题目描述
每个房间里有若干钥匙(通往别的房间)。从 0 号房开始，能否访问到所有房间？
rooms = [[1], [2], [3], []]
输出 = true
思路解析
把房间看成节点、钥匙看成有向边。从 0 开始 DFS，用一个 visited 记下哪些房间去过了。最后数一下 visited，等于房间总数就 true。
建图 · 从 0 出发：先画成图，房间就是节点。从 0 进去，标记成已访问（图上变绿）。它手里有把钥匙，能去 1 号房。
用 0 的钥匙 → 访问 1：拿 0 的钥匙去开 1 的门，进去标记已访问。1 房里又有钥匙，指向 2。
→ 访问 2：再用 1 的钥匙开 2，标记已访问。2 房也有钥匙，能去 3。
→ 访问 3 · 全到齐：开到 3，标记。3 房没钥匙了，这条路走到头。
判断：数一下去过的房间：4 个，正好等于总数，说明全都能到，返回 true。要是有房间没去过，就返回 false。
凡是「从一个点出发能不能走到所有点」「有几个连通块」这种，都能用 DFS/BFS 数可达节点。钥匙房间、被围住的区域、省份数量，都是这一类。
参考代码（Python）
Python
1visited = set()
2def dfs(room):
3 visited.add(room)
4 for key in rooms[room]: # 房里的每把钥匙
5 if key not in visited: # 没去过的房间
6 dfs(key)
7dfs(0)
8return len(visited) == len(rooms)复杂度分析
- 时间复杂度：O(N+E) —— 房间数 + 钥匙总数
- 空间复杂度：O(N) —— visited + 递归栈
套路模板
模板背下来：visited 标记、邻居只递归没去过的、最后数一下 visited。把递归换成队列，就是 BFS，效果一样。
Python
1visited = set()
2def dfs(u):
3 visited.add(u)
4 for v in graph[u]:
5 if v not in visited: dfs(v) # 只走没访问的
6dfs(start)
7# len(visited) == N ? 全连通易错点
- ❌ 进 dfs 不立刻标记 → ✅ 一进入就加 visited（否则有环时会无限递归）
- ❌ 判断只看"有没有走到终点" → ✅ 比对 len(visited)==N（题目要的是访问到全部房间）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。