Question 2 Keys and Rooms
Question
Step 1: 分析问题
this is a graph problem
vertical: room
edge: the key from the current room
Step 2: 声明是图中间什么问题
reachable problem in the graph
Step 3: method: dfs + bfs
图论中,题目提到1,n: there are n rooms(nodes) labeled from 0 to n-1 ==> please use an array to mark visited or other
public boolean canVisitedAllRooms(List<List<Integer>> rooms) {
Set<Integer> visited = new HashSet<>();
int totalNumberOfRoomsNeedsToVisit = rooms.size();
dfs(rooms, 0, visited); //一定要注意图不一定是联通的
bfs(rooms, 0, visited);
return visited.size() == totalNumberOfRoomsNeedsToVisit;
}
private dfs(List<List<Integer>> rooms, int current, Set<Integer> visited) {
if (visited.contains(current)) {
return;
}
visited.add(current);
List<Integer> neis = rooms.get(current);
if (!neis.isEmpty()) {
for (Integer nei: neis) {
dfs(rooms, nei, visited);
}
}
}
private void bfs(List<List<Integer>> rooms, int current, Set<Integer> visited) {
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(current);
visited.add(current);
while (!queue.isEmpty()) {
int cur = queue.poll();
List<Integer> neis = rooms.get(cur);
if (!neis.isEmpty()) {
for (Integer nei: neis) {
if (!visited.contains(nei)) {
queue.offer(nei);
visited.add(nei);
}
}
}
}
}
Last updated