題目與適用情境
有 n 個節點，編號為 0 到 n - 1。初始時每個節點各自形成一個連通分量。請實作 UnionFind，支援以下操作：
union(a, b)：合併a和b所在的分量；只有原本不同的兩個分量真的合併時才回傳
True。
connected(a, b)：判斷兩個節點目前是否屬於同一分量。count()：回傳目前的連通分量數量。
本題允許 n = 0，但任何操作參數都必須是合法編號，否則拋出 IndexError。基礎題只增加連線， 不刪除邊；呼叫由單一執行緒完成。例如 n = 6 時依序合併 (0, 1)、(1, 2)、(3, 4)， 目前有 3 個分量：{0, 1, 2}、{3, 4} 和 {5}。再合併 (2, 4) 後只剩 2 個；此時 union(0, 3) 應回傳 False，分量數不能再次減少。
這是一般軟體工程編碼面試中的資料結構題。核心情境是連線持續加入，同時穿插大量「是否連通」與 「還剩幾組」查詢。若所有邊一次給定、只需計算一次連通分量，DFS 或 BFS 通常更直接；能指出這項 差異也是題目的一部分。
面試官評估重點
第一項訊號是能否選對狀態。並查集不保存完整圖，而是把每個集合表示成一棵父指標樹；根節點代表該 集合，且根的父節點是自己。因此 connected(a, b) 可以簡化為比較兩個根，不必重新走訪所有邊。
第二項訊號是合併是否只連接根。直接寫 parent[a] = b 可能把一棵樹的中間節點改掛到另一節點， 破壞原集合的結構。正確步驟是先求 roota 與 rootb，確認兩根不同，再把較小樹的根掛到較大樹 的根。size 只對根有定義，用來控制樹高。
第三項訊號是能否解釋路徑壓縮，而非只背模板。本實作採用路徑折半：find 往根移動時，讓目前節點 改指向祖父節點。新父節點仍在同一棵樹中，因此連通關係不變；後續查找路徑會縮短。路徑折半以迴圈 完成，也避開長路徑上的遞迴深度問題。
最後會檢查計數不變量、複雜度口徑和驗證意識。components 初始為 n，只在兩個不同根合併後減一； 重複合併和自己與自己合併都不能改變它。按大小合併與路徑壓縮同時使用時，單次操作在一串操作上的 均攤時間為 O(α(n))，並非每次呼叫都嚴格是 O(1)。
回答前需要釐清的問題
- 連線只會增加，還是也會刪除？ 只增加時使用標準並查集。任意刪除一條邊後，剩餘邊是否仍讓
兩點連通無法從父指標森林恢復，需要離線演算法或更複雜的動態連通結構。
- 查詢會在線穿插，還是所有邊一次給定？ 在線合併與連通查詢適合並查集；靜態圖只做一次分量
統計時，鄰接串列加 DFS/BFS 的 O(n + m) 解法更直觀，也保留實際邊。
union的回傳值是什麼？ 本題回傳是否真的合併。這個布林值可以直接用於環偵測，也能保證
分量計數只更新一次。
- 非法節點如何處理？ 本題拋出
IndexError。如果呼叫端保證編號合法，可以刪除檢查以縮短
競賽程式碼；不能讓 Python 的負索引悄悄指向陣列尾端。
- 需要查詢分量大小或列出成員嗎？ 根上的
size能以近似常數的均攤時間回答大小；列出全部
成員仍至少與輸出量成正比，基礎並查集沒有維護成員清單。
- 是否有並行呼叫？ 基礎實作會在
find中寫入父陣列，連查詢都不是唯讀，也不具執行緒安全性。
若必須並行，需要定義鎖定範圍或選用專門的並行並查集演算法。
30 秒回答架構
「我用兩個長度為 n 的陣列：parent[x] 指向父節點，size[root] 記錄根所在樹的大小；初始每個 節點的父節點是自己，分量數是 n。find 沿父指標找根，途中讓節點改指向祖父節點做路徑折半。 union 先找兩個根；相同就回傳 False，不同則把較小樹的根掛到較大樹的根，累加大小，把分量數 減一並回傳 True。連接兩個根不會產生環，路徑折半只在原集合內修改父指標，所以連通關係維持 正確。初始化是 O(n)，之後每次操作均攤 O(α(n))，空間是 O(n)。」
分步深入解答
最直接的表示法是替每個節點保存一個分量編號。connected 只需比較兩個編號，但合併兩個分量時 必須掃描整個陣列，把舊編號全部改成新編號，單次 union 會達到 O(n)。另一種樸素方案只用父 指標樹，卻總把一棵根掛到另一棵根而不控制大小；一串不利的合併會形成長鏈，使 find 退化。
建議方案維護三項狀態：
parent[x]是x的父節點，且每棵樹的根滿足parent[root] == root。size[root]是該根對應分量的節點數；非根位置的舊值不再讀取。components等於父指標森林中的根數量。
實作如下。_validate 很短且只在此類別使用，因此留在使用位置附近，不另外抽成工具模組。
class UnionFind:
def __init__(self, n: int) -> None:
if n < 0:
raise ValueError("n must be non-negative")
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def _validate(self, x: int) -> None:
if x < 0 or x >= len(self.parent):
raise IndexError("node out of range")
def find(self, x: int) -> int:
self._validate(x)
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a: int, b: int) -> bool:
root_a = self.find(a)
root_b = self.find(b)
if root_a == root_b:
return False
if self.size[root_a] < self.size[root_b]:
root_a, root_b = root_b, root_a
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
self.components -= 1
return True
def connected(self, a: int, b: int) -> bool:
return self.find(a) == self.find(b)
def count(self) -> int:
return self.components正確性可以分三步說明。初始化時每個節點是唯一根，森林包含 n 棵單節點樹，三項不變量都成立。 路徑折半把 x 的父節點改為原父節點的父節點；祖父仍在同一條通往原根的路徑上，所以不會跨集合， 也不會改變 find(x) 的最終根。
合併時只操作兩個根。若根相同，兩節點已經連通，狀態不變。若根不同，把 root_b 指向 root_a 會把兩棵樹連成一棵，而且不可能成環，因為兩根原本屬於不同樹；新根大小等於兩棵樹大小 總和，根數量恰好減一。依此歸納，兩個節點連通若且唯若 find 回傳同一根，count() 始終等於 真實分量數。
按大小合併保證一個節點每次因整棵樹被掛到別處而增加深度時，它所在分量的大小至少加倍；即使不做 路徑壓縮，樹高也至多是 O(log n)。再結合路徑折半，一串 m 次查找和合併在初始化後總計具有 O(m α(n)) 的均攤界。α 是反阿克曼函數，成長極慢；面試中可以說「近似常數均攤時間」，但不應 改寫成嚴格的最壞 O(1)。兩個陣列占 O(n) 空間，迴圈式 find 的額外堆疊空間是 O(1)。
可以用下列操作手動追蹤狀態：
n = 6 count = 6
union(0, 1) -> True count = 5
union(1, 2) -> True count = 4
union(3, 4) -> True count = 3
connected(0, 2) -> True
connected(0, 4) -> False
union(2, 4) -> True count = 2
union(0, 3) -> False count = 2驗證不能只看一個範例。至少涵蓋 n = 0 且不呼叫查詢、n = 1 的自己合併、重複合併、兩個獨立 分量再以一條邊橋接、孤立節點、用相反順序反覆合併，以及 -1 和 n 兩個非法編號。對隨機小圖， 還可以維護一份鄰接串列，每次加邊後用 BFS 計算連通性和分量數，與並查集逐步比對；這是很有效的 差分測試。
若所有 m 條邊一開始就已知，而且只問一次分量數，建立鄰接串列後從每個未走訪節點做 DFS/BFS， 時間和空間都是 O(n + m)，程式碼意圖也很清楚。並查集的優勢出現在邊逐條到來、查詢與合併交錯， 或需要在 Kruskal 演算法中快速判斷加入無向邊是否成環。選擇依據是操作模型，不是「看到圖就用 並查集」。
高品質示範回答
「我先確認關係只會新增、查詢會和新增操作交錯，而且 union 要回傳是否真的合併。這樣我會用 並查集；如果只是靜態圖的一次分量統計，DFS 會更直接。
狀態包含 parent、根節點上的 size 和目前根數量 components。初始每個節點指向自己。 find 以迴圈往根移動，每走一步把目前節點改指向祖父，既縮短路徑，也避開遞迴深度問題。union 取得兩根後，如果相同就回傳 False，不改計數；否則把較小樹的根掛到較大樹根上，累加大小並把 計數減一。
這個實作始終是一片森林。路徑折半只把節點連向同一棵樹中的祖先；合併只連接兩棵不同樹的根，所以 不會形成父指標環。每次成功合併恰好把兩棵樹變成一棵，因此分量數也正確。
建立兩個陣列需要 O(n)。按大小合併配合路徑折半後，查找、連通判斷和合併的時間都是 O(α(n)) 均攤，空間是 O(n)。我會重點測試自己合併與重複合併不減少計數、橋接兩個大分量、 孤立節點、空結構和非法負索引；隨機小規模下再用 BFS 作為參照進行差分驗證。」
常見錯誤
- 直接設定
parent[a] = b→a可能不是根，原樹的一部分被錯誤拆開或形成難以控制的長鏈
→ 先分別 find，只連接兩個根。
- 每次都讓第二棵樹掛到第一棵樹 → 不利順序會製造長路徑 → **按根上的
size或rank
合併。**
find只回傳parent[x]→ 父節點未必是根，間接連通會被誤判 → 沿父指標走到自指根。- 成功或失敗都執行
components -= 1→ 重複合併和自己合併會讓計數愈來愈小 → **只在兩根
不同時更新計數。**
- 交換根後仍更新舊變數的大小 →
size與實際樹結構分離 → **先決定最終父根，再統一連接和
累加。**
- 宣稱每次操作最壞
O(1)→ 複雜度保證針對操作序列且包含反阿克曼函數 → **回報
O(α(n)) 均攤。**
- 忽略 Python 負索引 →
find(-1)會存取最後一個節點而非報錯 → 公開實作明確檢查上下界。 - 把並查集用於任意刪邊 → 父指標沒有保存替代路徑，無法判斷刪除後是否斷開 → **改用離線刪除
處理、回滾並查集或動態連通結構。**
- 把
connected當成唯讀方法 → 路徑折半會寫入parent，並行呼叫可能競爭 → **先定義同步
契約，再選擇全域鎖、分區方案或並行演算法。**
追問與應對
追問 1：如何用並查集偵測無向圖中的環？
逐條處理邊 (u, v)。若 union(u, v) 回傳 False，兩端在加邊前已經連通，新邊會封閉一個環； 若回傳 True，它只是連接兩個原本分開的分量。這個規則只直接適用於無向圖；有向圖的環偵測應使用 三色 DFS、拓撲排序等方法。
追問 2：如果要支援撤銷最近一次合併呢？
使用回滾並查集：保留按大小合併，並把每次真實修改前的父節點、根大小和分量數記錄到堆疊，撤銷時 還原。通常不做路徑壓縮，因為一次 find 會修改路徑上的多個位置，使回滾紀錄膨脹且邊界變複雜。 只按大小合併仍能把樹高限制在 O(log n)，適合配合時間線分治處理離線動態連通。
追問 3：如果關係可以任意刪除呢？
標準並查集不能在線回答任意刪邊。若整段操作預先已知，可以把每條邊的有效時間區間放入時間線線段樹， 走訪時配合回滾並查集；只在結尾刪除的邊也可以倒序轉成加邊。真正在線且高頻的插入、刪除和查詢需要 更複雜的全動態連通資料結構。面試中應先確認操作是否離線，因為這會決定問題等級。
追問 4：如何回傳某個分量的大小或全部成員？
大小已經保存在根上，可以實作 size_of(x) = size[find(x)]，均攤時間不變。列出成員不能只靠根大小； 掃描全部節點並比較根需要 O(n α(n))，額外維護成員集合又會增加合併成本和記憶體。若需求只是偶爾 匯出，掃描通常更簡單；若每次合併後都要列舉成員，應重新評估資料結構。
追問 5：多個執行緒並行呼叫時如何處理？
最小正確改法是用一把互斥鎖包住 find、union 和 connected，因為路徑折半會寫父陣列；這樣 容易證明，但會序列化全部操作。只有效能量測證明它是瓶頸時，才值得採用以原子比較交換、確定性掛接 順序或分區為基礎的並行並查集。並行版本必須重新證明父指標無環、大小更新與分量計數的原子性，不能 只把陣列換成原子型別。