Description#
There are n
rooms labeled from 0
to n  1
and all the rooms are locked except for room 0
. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms
where rooms[i]
is the set of keys that you can obtain if you visited room i
, return true
if you can visit all the rooms, or false
otherwise.
Example 1:
Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
Constraints:
n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
 All the values of
rooms[i]
are unique.
Solutions#
Solution 1: DepthFirst Search (DFS)#
We can use the DepthFirst Search (DFS) method to traverse the entire graph, count the number of reachable nodes, and use an array vis
to mark whether the current node has been visited to prevent repeated visits.
Finally, we count the number of visited nodes. If it is the same as the total number of nodes, it means that all nodes can be visited; otherwise, there are nodes that cannot be reached.
The time complexity is $O(n + m)$, and the space complexity is $O(n)$, where $n$ is the number of nodes, and $m$ is the number of edges.
1
2
3
4
5
6
7
8
9
10
11
12
 class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) > bool:
def dfs(i: int):
if i in vis:
return
vis.add(i)
for j in rooms[i]:
dfs(j)
vis = set()
dfs(0)
return len(vis) == len(rooms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 class Solution {
private int cnt;
private boolean[] vis;
private List<List<Integer>> g;
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
g = rooms;
vis = new boolean[g.size()];
dfs(0);
return cnt == g.size();
}
private void dfs(int i) {
if (vis[i]) {
return;
}
vis[i] = true;
++cnt;
for (int j : g.get(i)) {
dfs(j);
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int n = rooms.size();
int cnt = 0;
bool vis[n];
memset(vis, false, sizeof(vis));
function<void(int)> dfs = [&](int i) {
if (vis[i]) {
return;
}
vis[i] = true;
++cnt;
for (int j : rooms[i]) {
dfs(j);
}
};
dfs(0);
return cnt == n;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 func canVisitAllRooms(rooms [][]int) bool {
n := len(rooms)
cnt := 0
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if vis[i] {
return
}
vis[i] = true
cnt++
for _, j := range rooms[i] {
dfs(j)
}
}
dfs(0)
return cnt == n
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 function canVisitAllRooms(rooms: number[][]): boolean {
const n = rooms.length;
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number) => {
if (vis[i]) {
return;
}
vis[i] = true;
for (const j of rooms[i]) {
dfs(j);
}
};
dfs(0);
return vis.every(v => v);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 impl Solution {
pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) > bool {
let n = rooms.len();
let mut is_open = vec![false; n];
let mut keys = vec![0];
while !keys.is_empty() {
let i = keys.pop().unwrap();
if is_open[i] {
continue;
}
is_open[i] = true;
rooms[i].iter().for_each(&key keys.push(key as usize));
}
is_open.iter().all(&v v)
}
}
