Keys and Rooms Solutions in C++

/// Source : https://leetcode.com/problems/keys-and-rooms/description/
/// Author : liuyubobobo
/// Time   : 2018-09-30

#include <iostream>
#include <vector>

using namespace std;


/// DFS
/// Time Compexity: O(V + E)
/// Space Complexity: O(V)
class Solution {

public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {

        int V = rooms.size();
        vector<bool> visited(V, false);
        return dfs(rooms, 0, visited) == V;
    }

private:
    int dfs(const vector<vector<int>>& rooms, int v, vector<bool>& visited){

        visited[v] = true;

        int res = 1;
        for(int next: rooms[v])
            if(!visited[next])
                res += dfs(rooms, next, visited);
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/keys-and-rooms/description/
/// Author : liuyubobobo
/// Time   : 2018-09-30

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


/// BFS
/// Time Compexity: O(V + E)
/// Space Complexity: O(V)
class Solution {

public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {

        int V = rooms.size();
        vector<bool> visited(V, false);

        int res = 0;
        queue<int> q;
        q.push(0);
        visited[0] = true;
        while(!q.empty()){
            int cur = q.front();
            q.pop();

            res ++;

            for(int next: rooms[cur])
                if(!visited[next]){
                    visited[next] = true;
                    q.push(next);
                }
        }

        return res == V;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/keys-and-rooms/description/
/// Author : liuyubobobo
/// Time   : 2018-09-30

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


/// DFS
/// Using Stack - non recursion algorithm
///
/// Time Compexity: O(V + E)
/// Space Complexity: O(V)
class Solution {

public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {

        int V = rooms.size();
        vector<bool> visited(V, false);

        int res = 0;
        stack<int> stack;
        stack.push(0);
        visited[0] = true;
        while(!stack.empty()){
            int cur = stack.top();
            stack.pop();

            res ++;

            for(int next: rooms[cur])
                if(!visited[next]){
                    visited[next] = true;
                    stack.push(next);
                }
        }

        return res == V;
    }
};


int main() {

    return 0;
}