Easy

1971. Find if Path Exists in Graph

depth-first-searchbreadth-first-searchunion-findgraph

解題說明

Find if Path Exists in Graph

題目描述：給定一個無向圖，包含 n 個節點和一組邊，判斷從節點 source 到節點 destination 是否存在路徑。

解題思路：這是基本的圖連通性問題。可以使用 Union-Find（並查集）解決：遍歷所有邊將端點合併，最後檢查 source 和 destination 是否在同一集合。Union-Find 的路徑壓縮和按秩合併使得每次操作近乎 O(1)。也可以用 BFS 或 DFS，但 Union-Find 實作最為簡潔。

C++ 解法

複雜度分析

時間複雜度：O(E × α(n)) — E 為邊數，α 為反阿克曼函數（近乎常數）。

空間複雜度：O(n) — Union-Find 的 parent 和 rank 陣列。

虛擬碼

1. Initialize Union-Find: parent[i] = i for all i
2. For each edge (u, v):
   a. Union(u, v)
3. Return Find(source) == Find(destination)

其他解法

BFS：從 source 出發做廣度優先搜索，若能到達 destination 則回傳 true。時間 O(V + E)，空間 O(V + E)（鄰接表 + visited 陣列）。

DFS：從 source 出發做深度優先搜索。時間 O(V + E)，遞迴版本可能在深圖上棧溢出，迭代版本更安全。

延伸思考

若圖是有向的，如何判斷 source 到 destination 的可達性？
若要找出最短路徑（邊數最少），BFS 和 Union-Find 哪個更適合？
若邊會動態新增或刪除，如何維護連通性查詢？

Find if Path Exists in Graph — CaffeCode