---
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]]
```
-->