題目描述:給定 n 個節點和邊列表(無向圖),計算連通分量的數量。
解題思路:使用 Union-Find:初始時每個節點是獨立分量(共 n 個)。對每條邊,若兩端節點不在同一分量,合併並將計數減一。最終計數即為連通分量數。也可用 DFS/BFS:從每個未訪問的節點出發做一次完整搜尋,計數搜尋次數。
時間複雜度:O((n + E) × α(n)) ≈ O(n + E)。
空間複雜度:O(n) — parent 和 rank 陣列。
1. Initialize Union-Find: each node is its own component, total = n 2. For each edge (u, v): a. If find(u) != find(v): unite, components-- 3. Return components
BFS O(N+E) 時間,O(N) 空間:用隊列代替遞迴棧 — 邏輯相同。
並查集 (Union-Find) O(N α(N)) 時間,O(N) 空間:為每條邊合併節點,計算不同的父節點 — 時間複雜度更優,常數更大。