題目描述:給定 n 個節點和 edges 列表,判斷這些節點和邊是否構成一棵有效的樹。
解題思路:有效樹的兩個條件:(1)恰好有 n-1 條邊;(2)所有節點連通(無環)。先檢查邊數,再用 Union-Find(或 DFS)確認連通性與無環。Union-Find:對每條邊,若兩端節點已在同一集合中則有環;否則合併。最後確認只有一個連通分量。
時間複雜度:O(E × α(n)) ≈ O(E) — Union-Find 幾乎為常數時間(反阿克曼函數)。
空間複雜度:O(n) — parent 和 rank 陣列。
1. If edges.size() != n - 1: return false 2. Initialize Union-Find with n nodes 3. For each edge (u, v): a. If find(u) == find(v): cycle detected, return false b. Else: union(u, v) 4. Return true (n-1 edges, no cycle → connected tree)
DFS O(N+E):遞迴訪問所有節點,檢查無環且連通 — 邏輯略不同但時間複雜度相同。
並查集 (Union-Find) O(N α(N)):為每邊構造並查集,檢查是否形成新連通分量或產生環 — 更直觀且易於推廣。