LeetCode 841. 钥匙和房间

◎

本节目标

从房间 0 迭代 DFS，比较已访问房间数与总房间数。

这是图的表示与遍历中已给出邻接表的可达性判断：第 i 个数组就是房间 i 的出边列表。

查看 LeetCode 原题

题意与约束

从房间 0 开始，进入一个房间后可以拿到其中所有钥匙。判断能否进入全部房间。钥匙关系可形成环，也可能有永远拿不到钥匙的房间；只有一个空房间时答案为真。

直接思路与瓶颈

可以不断扫描所有“已经可进入”的房间，把新钥匙加入集合，直到集合不再增长。若每轮都重新扫描已经处理过的房间和钥匙，会重复工作，也难以保证每把钥匙只处理一次。

图模型与算法推导

直接把 rooms 视为邻接表。将房间 0 标记并压栈，每弹出一个房间就累加访问数量；对其中每把钥匙，若对应房间未访问，则立刻标记并压栈。遍历结束后，访问数等于总房间数就说明所有房间可达。

正确性依据

不变量是：已访问的房间都能从 0 沿已获得钥匙序列进入，栈中的房间已被发现但尚未展开。初始化的房间 0 成立；从已访问房间拿到的钥匙只能打开一个新的可达房间，因此每次扩张保持不变量。所有可达房间都会在其前驱房间被展开时入栈，最终计数恰是从 0 可达的顶点数。

样例执行过程

对 rooms = [[1,2],[3],[3],[]]，初始化 stack = [0]、visited = {0}、visitedCount = 0。弹出 0 后计数为 1，取得钥匙 1、2，立即标记并压栈，栈为 [1,2]。弹出 2 后计数为 2，钥匙 3 使栈变为 [1,3]；弹出 3 后计数为 3；最后弹出 1，虽然再次看到钥匙 3，但它已访问，计数最终为 4。它等于房间总数，返回 true。

代码实现

C++

C++17

#include <vector>

using namespace std;

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false);
        vector<int> stack{0};
        visited[0] = true;
        int visitedCount = 0;

        while (!stack.empty()) {
            int room = stack.back();
            stack.pop_back();
            ++visitedCount;
            for (int key : rooms[room]) {
                if (!visited[key]) {
                    visited[key] = true;
                    stack.push_back(key);
                }
            }
        }
        return visitedCount == static_cast<int>(rooms.size());
    }
};

Python

Python 3

class Solution:
    def canVisitAllRooms(self, rooms):
        visited = [False] * len(rooms)
        stack = [0]
        visited[0] = True
        visited_count = 0

        while stack:
            room = stack.pop()
            visited_count += 1
            for key in rooms[room]:
                if not visited[key]:
                    visited[key] = True
                    stack.append(key)
        return visited_count == len(rooms)

实现将 visited 数量单独计数；即便环中的钥匙反复出现，入栈时的标记也保证每个房间只计一次。

复杂度分析

每个房间和每把钥匙至多处理一次，时间复杂度为 O(V + E)；visited 与栈的额外空间为 O(V)。

边界与易错点

• 必须从房间 0 开始，不能把所有房间都当作 DFS 起点。
• 只有一个房间时，空钥匙列表仍表示已经访问全部房间。
• 发现钥匙时即标记，避免环让同一房间重复入栈。
• 返回条件是访问数等于 rooms.size()，不是“最后一个房间是否访问”。

模式迁移

把房间替换为课程、服务依赖或网页链接，问题仍是从指定入口能覆盖多少状态；若还需要给出不可达状态或层数，可在同一 visited 结构上追加集合收集或 BFS 距离。