--- tags: leetcode --- # [841. Keys and Rooms](https://leetcode.com/problems/keys-and-rooms/) --- # My Solution ## Solution 1: DFS ### The Key Idea for Solving This Coding Question ### C++ Code 1 ```cpp= #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 ```cpp= #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 ```cpp= #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 <!-- # Test Cases ``` [[1],[2],[3],[]] ``` ``` [[1,3],[3,0,1],[2],[0]] ``` ``` [[4],[3],[],[2,5,7],[1],[],[8,9],[],[],[6]] ``` -->