841. Keys and Rooms

---

My Solution

Solution 1: DFS

The Key Idea for Solving This Coding Question

C++ Code 1

#define WHITE (1)  // not visited
#define GRAY  (2)  // visiting the node and its descendants
#define BLACK (3)  // have visited this node and all its descendants.

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int cnt = 0, n = rooms.size();
        vector<int> state(n, WHITE);
        
        dfs(rooms, state, 0, cnt);
        return cnt == n;
    }
    
private:
    void dfs(vector<vector<int>> &rooms, vector<int> &state, int currRoom, int &cnt) {
        state[currRoom] = GRAY;
        ++cnt;
        
        for (int i = 0; i < rooms[currRoom].size(); ++i) {
            if (state[rooms[currRoom][i]] != WHITE) {
                continue;
            }
            dfs(rooms, state, rooms[currRoom][i], cnt);
        }
        
        state[currRoom] = BLACK;
    }
};

Time Complexity

$O(n)$

• $n$ is the lenght of rooms.

Space Complexity

$O(H)$

• $H$ is the height while we traverse the graph described by rooms.
• In the worst case, the space complexity is
  $O(n)$.

C++ Code 2

#define WHITE (1)
#define GRAY  (2)
#define BLACK (3)

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size(), cnt = 0;
        vector<int> state(n, WHITE);
        
        for (int i = 0; i < n; ++i) {
            if (state[i] == WHITE) {
                dfs(rooms, state, i);
                ++cnt;
            }
        }
        
        return cnt == 1;
    }
    
private:
    void dfs(vector<vector<int>> &rooms, vector<int> &state, int currRoom) {
        state[currRoom] = GRAY;
        
        vector<int> &nextRooms = rooms[currRoom];
        int n = nextRooms.size();
        for (int i = 0; i < n; ++i) {
            if (state[nextRooms[i]] != WHITE) {
                continue;
            }
            dfs(rooms, state, nextRooms[i]);
        }
        
        state[currRoom] = BLACK;
    }
};

Time Complexity

$O(n)$

• $n$ is the lenght of rooms.

Space Complexity

$O(H)$

• $H$ is the height while we traverse the graph described by rooms.
• In the worst case, the space complexity is
  $O(n)$.

Solution 2: BFS

The Key Idea for Solving This Coding Question

C++ Code

#define WHITE (1)  // not visited
#define GRAY  (2)  // visiting the node and its descendants
#define BLACK (3)  // have visited this node and all its descendants.

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int cnt = 1, n = rooms.size();
        vector<int> state(n, WHITE);
        queue<int> q;
        
        q.push(0);
        state[0] = GRAY;
        while (!q.empty()) {
            int currRoom = q.front();
            q.pop();
            
            for (int i = 0; i < rooms[currRoom].size(); ++i) {
                if (state[rooms[currRoom][i]] != WHITE) {
                    continue;
                }
                q.push(rooms[currRoom][i]);
                state[rooms[currRoom][i]] = GRAY;
                ++cnt;
            }
            state[currRoom] = BLACK;
        }
        
        return cnt == n;
    }
};

Time Complexity

$O(n)$

• $n$ is the lenght of rooms.

Space Complexity

$O(n)$

Miscellane