Keys and Rooms

題目描述

有 n 個房間（0 到 n-1），一開始你在房間 0。每個房間有一組鑰匙 rooms[i]，可以打開對應的房間。回傳是否能進入所有房間。

輸入: rooms = [[1],[2],[3],[]]
輸出: true
解釋: 0→1→2→3，全部可達

輸入: rooms = [[1,3],[3,0,1],[2],[0]]
輸出: false
解釋: 無法進入房間 2

解題思路

從房間 0 開始

將 0 加入 Stack 和 visited Set，作為 DFS 起點

DFS 探索

pop 出一個房間，遍歷該房間的所有鑰匙，對未訪問的房間 push 到 Stack

標記已訪問

用 HashSet.Add(key) 同時完成「是否新房間」的判斷和標記，一行搞定

檢查結果

Stack 為空時 DFS 結束，比較 visited.Count 和 rooms.Count 是否相等

程式碼

C#

csharp

public class Solution {
    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
        var visited = new HashSet<int> { 0 };
        var stack = new Stack<int>();
        stack.Push(0);
 
        while (stack.Count > 0) {
            int room = stack.Pop();
            foreach (int key in rooms[room]) {
                if (visited.Add(key)) { // 如果是新房間
                    stack.Push(key);
                }
            }
        }
        return visited.Count == rooms.Count;
    }
}

TypeScript

typescript

function canVisitAllRooms(rooms: number[][]): boolean {
    const visited = new Set<number>([0]);
    const stack: number[] = [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;
}

Python

python

def canVisitAllRooms(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)

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n + e) | O(n) |

n 是房間數，e 是鑰匙總數（邊數）。Time O(n + e) 是因為每個房間最多入 Stack 一次、每把鑰匙最多被檢查一次。Space O(n) 是因為 visited Set 和 Stack 最多各存 n 個房間。

邊界情況

只有一個房間：rooms = [[]]，起點就是唯一房間，visited.Count == 1 == rooms.Count，回傳 true
房間 0 沒有鑰匙：rooms = [[], [0]]，只能待在房間 0，無法到達房間 1，回傳 false
存在環但有孤島：如 rooms = [[1], [0], []]，0 和 1 互通但房間 2 無法到達，回傳 false

圖解

Room 0 [1]

key 1→

Room 1 [2]

key 2→

Room 2 [3]

key 3→

Room 3 []

圖表展示了 [[1],[2],[3],[]] 的完整可達路徑：從 Room 0 拿到 key 1 開 Room 1，再拿 key 2 開 Room 2，最後拿 key 3 開 Room 3。所有房間都標為 highlight 代表全部可達。

進階觀點

💡面試追問

Q: DFS 和 BFS 在這題的差異？ A: 複雜度相同 O(n + e)。DFS 用 Stack 或遞迴，程式碼較短；BFS 用 Queue，遍歷順序不同但結果一樣。面試中選一種寫，口頭說明另一種即可。

Q: 這題的圖論本質是什麼？ A: 有向圖的可達性問題。rooms[i] 定義了從節點 i 出發的有向邊集合。問題等價於「從節點 0 出發，DFS/BFS 能否訪問到所有 n 個節點」。

Q: 如果要找出無法到達的房間列表怎麼做？ A: DFS 結束後遍歷 0 到 n-1，不在 visited Set 中的就是無法到達的房間。額外 O(n) 時間。

變體題：LC 547 Number of Provinces（無向圖連通分量）、LC 1466 Reorder Routes（有向圖方向問題）。

理解測驗

🤔 這題的本質是什麼圖論問題？

🤔 為什麼需要 visited 集合？