1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Deque<Integer> availableRooms = new ArrayDeque<>();
boolean[] visited = new boolean[rooms.size()];
visited[0] = true;
availableRooms.offer(0);
int roomCount = 1;
while (!availableRooms.isEmpty()) {
int currRoom = availableRooms.poll();
for (Integer key : rooms.get(currRoom)) {
if (!visited[key]) {
availableRooms.offer(key);
visited[key] = true;
roomCount += 1;
}
}
}
return roomCount == rooms.size();
}
}
|
直接bfs.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private int roomCount;
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] visited = new boolean[rooms.size()];
dfs(0, rooms, visited);
return roomCount == rooms.size();
}
private void dfs(int currRoom, List<List<Integer>> rooms, boolean[] visited) {
if (visited[currRoom]) {
return;
}
visited[currRoom] = true;
roomCount += 1;
List<Integer> keys = rooms.get(currRoom);
for (Integer key : keys) {
dfs(key, rooms, visited);
}
}
}
|
也可以dfs.
时间复杂度和空间复杂度不变.
