管理「誰跟誰同一國」。合併集合、查連通,加了優化幾乎是 O(1)。
O(1),是「連通性」「分組」「Kruskal 最小生成樹」的神器。
每群是一棵樹 —— 用 parent 陣列表示:parent[x] 指向 x 的父節點,樹根指向自己。
根 = 代表 —— 同一群的元素,find 到最後都會走到同一個根。判斷同群就是「根一樣嗎」。
union = 把一棵樹掛到另一棵下 —— 找出兩邊的根,讓一個根指向另一個根。
find = 沿 parent 往上走到根 —— 一路走到 parent[x]==x 為止。
路徑壓縮(path compression) —— find 的時候順手把走過的節點直接接到根,樹越壓越扁,下次一步就到。
按大小 / 秩合併(union by size / rank) —— union 時把小的樹掛到大的樹下,避免長出細長的鏈。
兩個一起用 —— 每次操作攤還 O(α(n))(反阿克曼函數),n 再大 α(n) 都 ≤ 4,實務上就是 O(1)。
沒優化的話 —— 最壞會退化成一條鏈,find 變 O(n)。
🔗 判斷連通 / 數連通分量 —— 尤其適合「邊一條條加進來」的動態情況(比每次重跑 DFS 好)。
🔁 無向圖偵測環 —— union 兩端時發現已同根 → 這條邊造成環。
🌲 Kruskal 最小生成樹 —— 挑邊時用它避免成環。
👥 帳號合併、等價類分組、朋友圈 —— 任何「把有關係的併在一起再分組」的題。
6 個元素,一開始各自一國(每個是自己的根,虛線圈)。做幾次 union 把它們併起來(箭頭指向父/根),再 find(3) 沿箭頭走到根(琥珀路徑、綠根),最後看路徑壓縮怎麼把樹壓扁。按「下一步」。
從基本 find / union、路徑壓縮、按大小合併,到數連通分量、偵測環、Kruskal、朋友圈、帳號合併。
❌ 沒做任何優化 —— 純 union 不加路徑壓縮 / 按大小,最壞退化成鏈,find 變 O(n)。
❌ union 前忘了先 find 根 —— 要合併的是「兩邊的根」,不是元素本身;直接 parent[x]=y 會接錯。
❌ 想拿它做「拆散」 —— 它只擅長合併,不支援 union 的反操作(拆開很難)。要拆散另想辦法。
❌ 用在靜態一次性連通 —— 那 DFS / BFS 就夠了;並查集的優勢在「動態一直加邊 + 頻繁查連通」。
union(0,1)、union(2,3)、union(0,2) 之後,find(3) 走到哪個根?路徑壓縮做了什麼?把答案打到對話裡,我幫你對。