MediumRating 1477
2368. Reachable Nodes With Restrictions
arrayhash-tabletreedepth-first-searchbreadth-first-searchunion-findgraph
解題說明
Reachable Nodes With Restrictions
題目描述： 給定一棵 n 個節點的無向樹（n-1 條邊）和一組受限節點 restricted，從節點 0 出發，不經過受限節點，求可以到達的節點數量。
解題思路： 建立鄰接表，將受限節點放入集合以便 O(1) 查詢。從節點 0 開始做 BFS 或 DFS，遇到受限節點就跳過，計算可到達的節點數。
由於是樹結構（無環），不需要特別的 visited 陣列來防止重訪（用 parent 追蹤即可），但使用 visited 集合更簡潔。
C++ 解法
複雜度分析
時間複雜度：O(n) — 建圖 O(n) 加上 BFS 遍歷 O(n)
空間複雜度：O(n) — 鄰接表、visited 陣列和受限集合
虛擬碼
1. Build adjacency list from edges 2. Put all restricted nodes into a hash set 3. BFS from node 0: a. Mark node 0 as visited, count = 0 b. For each dequeued node u, increment count c. For each neighbor v of u: if not visited and not restricted, enqueue v 4. Return count
其他解法
-
DFS 遞迴法：用深度優先搜尋代替 BFS。對於樹結構來說邏輯更自然（不需要 visited，只需傳 parent 參數），但大規模輸入可能有遞迴深度問題。
-
Union-Find 法：將所有非受限節點之間的邊合併。最後返回包含節點 0 的連通分量大小。適合離線處理但對本題來說略為過度設計。
延伸思考
- 如果受限節點可以動態新增和移除，如何高效更新可達節點數？
- 如果要返回所有可達節點的列表（而非數量），最佳時間複雜度為何？
- 如果圖不是樹而是一般無向圖（可能有環），演算法需要如何調整？