841. 钥匙和房间
题目描述
有 n 个房间，编号 0 到 n - 1。只有 0 号房间没上锁，其余房间都要用钥匙才能进入。
输入数组 rooms，rooms[i] 是 i 号房间里放着的钥匙，每把钥匙上写着它能打开的房间号。进入一个房间后可以拿走其中所有钥匙，钥匙可以反复使用。
从 0 号房间出发。如果最终能进入每一个房间，返回 true，否则返回 false。
示例 1
输入：rooms = [[1],[2],[3],[]] 输出：true
解释：依次用钥匙 1、2、3 打开后面的房间，全部可以进入。
示例 2
输入：rooms = [[1,3],[3,0,1],[2],[0]] 输出：false
解释：没有任何房间里有钥匙 2，2 号房间进不去。
数据范围
n == rooms.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < n- 所有
rooms[i]中的值互不相同。
解题思路
把房间看作节点，房间 i 里有钥匙 k 就连一条 i → k 的有向边。问题变成：从节点 0 出发能否到达所有节点。用栈做 DFS：取出一个房间，遍历其中的钥匙，没开过的房间就标记为已访问并压栈。最后比较已访问数量和房间总数。
为什么正确
visited 中的房间都能从 0 号房间到达；栈里的房间是已经打开、但钥匙还没拿出来的房间。
复杂度分析
时间 O(n + 钥匙总数)，每个房间只进栈一次，每把钥匙只看一次。空间 O(n)。
易错点
要在压栈时就标记已访问，否则同一把钥匙出现在多个房间时，同一房间会被重复压栈。钥匙可能指向自己或已开过的房间，必须跳过。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = {0}
stack = [0]
while stack:
room = stack.pop()
for key in rooms[room]:
if key not in visited:
visited.add(key)
stack.append(key)
return len(visited) == len(rooms)class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Set<Integer> visited = new HashSet<>();
visited.add(0);
Deque<Integer> stack = new ArrayDeque<>();
stack.push(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();
}
}class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
vector<bool> visited(rooms.size(), false);
visited[0] = true;
int count = 1;
vector<int> stk = {0};
while (!stk.empty()) {
int room = stk.back();
stk.pop_back();
for (int key : rooms[room]) {
if (!visited[key]) {
visited[key] = true;
count++;
stk.push_back(key);
}
}
}
return count == (int)rooms.size();
}
};func canVisitAllRooms(rooms [][]int) bool {
visited := map[int]bool{0: true}
stack := []int{0}
for len(stack) > 0 {
room := stack[len(stack)-1]
stack = stack[:len(stack)-1]
for _, key := range rooms[room] {
if !visited[key] {
visited[key] = true
stack = append(stack, key)
}
}
}
return len(visited) == len(rooms)
}var canVisitAllRooms = function(rooms) {
const visited = new Set([0]);
const stack = [0];
while (stack.length > 0) {
const room = stack.pop();
for (const key of rooms[room]) {
if (!visited.has(key)) {
visited.add(key);
stack.push(key);
}
}
}
return visited.size === rooms.length;
};function canVisitAllRooms(rooms: number[][]): boolean {
const visited = new Set([0]);
const stack = [0];
while (stack.length > 0) {
const room = stack.pop()!;
for (const key of rooms[room]) {
if (!visited.has(key)) {
visited.add(key);
stack.push(key);
}
}
}
return visited.size === rooms.length;
}