There are n rooms numbered 0 to n-1. Each room has keys to other rooms. You start in room 0. Can you visit all rooms?
Input: [[1],[2],[3],[]] → Output: trueInput: [[1,3],[3,0,1],[2],[0]] → Output: false
BFS/DFS from room 0. Collect keys, visit newly accessible rooms. If all n rooms visited, return true.
- Start with keys from room 0.
- BFS: for each key in hand (unvisited room), visit it and collect its keys.
- Mark visited as we go.
- Return visited.size() == n.
import java.util.*;
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Set<Integer> visited = new HashSet<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0); visited.add(0);
while (!stack.isEmpty()) {
int room = stack.pop();
for (int key : rooms.get(room)) {
if (!visited.contains(key)) { visited.add(key); stack.push(key); }
}
}
return visited.size() == rooms.size();
}
}
- Time Complexity: O(V+E)
- Space Complexity: O(V)