## 定義
Disjoint set 中文為"互斥集、併查集"，從國/高中學過集合和集合相關的操作
所謂的互斥集就是**多個相互之間無交集的集合**，也就是每個集合包含的元素**皆不相同**
用例子去幫助理解
```
A = {1,2,4,5}
B = {3,6}
C = {7}
D = {1,9}
```
此時 A, B, C 為互斥集，B, C, D 為互斥集，但 A、D 因為有交集 $1$ 所以才不能放在一起
基於兩者作刪減的組合(例如 BCD 刪去 C 為 BD)也為互斥集
## 功能介紹
在大部分的情況中，只會讓互斥集中的集合做**合併**跟**查找**兩個動作
也因此催生出了一個新的名詞，也是互斥集的另外一個名稱"併查集"，功能詳細的描述如下
1. 合併: 兩個併查集合併成一個併查集
2. 查找: 判斷一個元素是否在併查集中或在哪一個併查集中
不過在**題目敘述**下，併查集的敘述可能是班級、團體、學校等等而非集合
## 儲存方式
這裡介紹兩種方法儲存併查集
1. 陣列索引
2. 樹狀圖(陣列)
以比賽的情況來說，通常是選擇第二個方式，因為樹狀圖有比較完整的功能
## 陣列索引儲存
陣列索引(index)儲存的好處就是非常**直觀**與**簡單**，第 $x$ 個人在團體 $y$ 中
比如上面的圖中，$0、4、5$ 是同一個團體的，因為它們的值都是 $2$，用程式表現如下
```cpp=
A[x] = y ; // index: x(第 x 個人) 在集合 y 中
```
時間複雜度，N 是總人數
1. 查找 : $O(1)$，直接用 index 查詢
2. 合併 : $O(N)$，需要找出單一團體所有人才能合併 $\rightarrow$ 遍歷全部
3. 找團體人數 : $O(N)$、$O(1)$ : 需用陣列儲存資料
空間複雜度 : $O(N)$ : 儲存併查集資料，$O(N)$ : 儲存團體人數
## 樹狀圖儲存方式
以根節點的編號作為團體編號，對於任何點來說，只要不斷往上找父節點，就可以找到該團體
一樣用一維陣列儲存資料，從圖上可以看出，索引 $x$ 對應的值 $y$ 是 $x$ 的父節點(學長)
而團長(圖中可以看出其實就是**樹的根**)的值就是**自己**，其餘人的值就是**父節點(學長)**
用程式表示查詢的功能就會像是這樣
```cpp=
int find_rec(int x) { // recursion
if (x != A[x]) // 目前只有學長(父節點)，沒有團長(根節點)
return find(A[x]) ; // 找團長
return x ; // 團長本人
}
int find_loop(int x) {
int nx = x ;
while (nx != A[nx]) // x 的值不是自己(只有團長是自己)
nx = A[nx] ; // 往父節點找
// nx 最後是 x 的團長(x 所在樹的根)
return nx ;
}
bool same_set(int x, int y) {
if (find(x) == find(y)) // x 跟 y 在同一個團體
return true ;
else // x 跟 y 不在同一個團體
return false ;
}
int main() {
// 初始化
for (int i=0;i<N;i++)
A[i] = i, S[i] = 1 ; // A 是併查集、S 是團體的人數
A[i] = j ; // i 的父節點是 j
return 0 ;
}
```
查找的功能需要找到**團體編號**，也就是團長，從剛剛的圖中可以知道，只有**團長**的值是自己
而不論你從樹(團體)中的哪個點找，只要一直往父節點(學長)找就可以找到根(團長)
所以配合這兩個條件就可以用程式達成查找功能，所以提供了迴圈解和遞迴解
遞迴解有一個優勢，就是能增加下次查找的效率，讓下次的同位置查找變成 $O(1)$
因為遞迴解是一層層找根再一層層回傳，所以每個"父節點"都會知道根節點是誰
這個方法叫路徑壓縮，要注意會**破壞樹的結構**，但會優化路徑上所有節點，實際的程式會如下
```cpp=
int find(int x) {
if (x != A[x]) { // 目前只有學長(父節點)，沒有團長(根節點)
int boss = find(A[x]) ; // 找到團長了(回傳值是團長)
A[x] = boss ; // 將"學長" 設成團長
return boss // 將團長資訊傳給學弟
}
return x ; // 團長本人
}
```
從點到根之間的所有點查詢都變成 $O(1)$，程式最簡寫會如下
```cpp=
int find(int x) {
return x == A[x] ? x : A[x] = find(A[x]) ;
}
```
但很明顯遞迴有一個限制，就是**深度**問題，所以很多極端情況還是只能用迴圈
好在迴圈也有對應的優化方式，也就是直接跳兩次父節點，也就是父節點的父節點
```cpp=
int find(int x) {
int nx = x ;
while (nx != A[nx]) { // x 的值不是自己(只有團長是自己)
A[nx] = A[A[nx]] ; // 學長的學長
nx = A[nx] ; // 學長
}
// nx 最後是 x 的團長(x 所在樹的根)
return nx ;
}
```
在多次查詢的情況下，最後路徑會被壓縮到 $O(1)$，因為每次路徑都除 $2$
---
如果 $x$ 所在的 set 跟 $y$ 所在的 set 要合併，只需要做兩個步驟
1. 確定新根節點是哪一個舊根節點或新開一個節點當根節點
2. 將舊的根節點接到新的根節點上
加上可能兩個團體**早就是同一個**了，所以要在最前面先判斷**兩人是否同一個團體**
```cpp=
void merge(int x, int y) {
int fx = find(x), fy = find(y) ; // 找出兩個團體的團長
if (fx == fy) return ; // 同團直接結束
int new_n = fx ; // 確定新團體團長為 fx(x 所在團體的團長)
A[fy] = fx ; // 將舊團長的學長改成新團長
}
```
如果這時候要數 $x$ 團長的團體總共有幾個人，可以用空間換時間
用一維陣列去儲存團長 $x$ 的團體有多少人，合併就相加
人數變化就跟上面大同小異，不過有一個優化還可以做，就是**合併層級優化**
在這邊會用到[樹的高度](https://hackmd.io/J8zW8mlSStCs3o9glWOSZw?view#%E6%A8%B9%E7%9A%84%E9%AB%98%E5%BA%A6)，如果不懂或是不熟就點進去看看定義
團體合併很明顯會造成一個問題，因為查找的效率變低了，所以誰當團長變得非常重要
從最左邊的圖來看，這兩個團體想要合併，會有中間或右邊的圖的方式
不同之處就是中間是 $1$ 當團長，右邊是 $5$ 當團長，而中間的樹高度是 $4$，右邊是 $3$
假設現在還沒做過查找優化，$7$ 找團長的路徑會是 $7、6、5、1$ 跟 $7、6、5$
應該看出效率上的差異了，如果較高的樹是被合併的一方，那查找的效率就會變低
從圖中可以看出，左樹如果被合併，新樹的高度就是 `max(左樹高度+1, 右樹高度)`
所以被合併的樹，應該要是**高度比較小**的樹，新樹的高度才會**最小**
但是其實在非高級別的競程上面，我建議用壓縮路徑的方式就好，不需要用到這個，有點浪費時間
時間複雜度(優化前)，N 是總人數、H 是樹的高度
1. 查找 : $O(H)\rightarrow O(N)$
2. 合併 : $O(H)\rightarrow O(N)$
3. 找團體人數 : $O(1)$
時間複雜度(兩個優化後)
1. 查找 : $O(log\ N)$，平均 : $O(\alpha(N))$
2. 合併 : $O(log\ N)$，平均 : $O(\alpha(N))$
3. 找團體人數 : $O(1)$
$\alpha(N)$ 目前不用會，把它當常數時間就好，有興趣[點這裡](https://zh.wikipedia.org/zh-tw/%E9%98%BF%E5%85%8B%E6%9B%BC%E5%87%BD%E6%95%B8#%E5%8F%8D%E5%87%BD%E6%95%B8)
空間複雜度 : $O(N)$ : 用來儲存併查集資料，$O(N)$ : 用來儲存團體人數
## 例題-f677. FJCU_109_Winter_Day3_Lab1 併查集練習
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f677)
從題目可以知道，要計算有多少人跟 $0$ 有接觸，也就是有多少人在 $0$ 的團體中
兩個人**有接觸**也就是**兩個團體合併**，所以要把合併功能加進去
因為編號只會是 $0\sim n-1$，所以就把數字小的當成團長( $0$ 必定是團長 )
最後把剛剛講過的併查集套到這題，題目沒給 $n$ 的範圍，用 $10005$ 能過
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[10005], S[10005] ; // A 併查集、S 團體人數
int find_root(int x) { // 查找團長
while (x != A[x])
x = A[x] ;
return x ;
}
void merge_tree(int x, int y) { // 合併團體
int fx = find_root(x), fy = find_root(y) ;
if (fx == fy) return ; // 同團體
if (fx > fy) {
S[fy] = S[fy] + S[fx] ; // 新團體人數是所有舊團體人數總和
A[fx] = fy ; // 更新團長
}
else {
S[fx] = S[fx] + S[fy] ; // 新團體人數是所有舊團體人數總和
A[fy] = fx ; // 更新團長
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, a, b ;
cin >> n >> m ;
for (int i=0;i<n;i++) // 初始化
A[i] = i, S[i] = 1 ;
for (int i=0;i<m;i++) {
cin >> a >> b ;
merge_tree(a, b) ; // 合併團體
}
cout << S[0] ; // 有多少人在 0 的團體中
return 0 ;
}
```
## 例題-d813. 10583 - Ubiquitous Religions
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d813)
每個人只能信一個教，也就是每個人都**只會**在一個團體
先假設有 $N$ 個宗教，如果發現**有宗教合併**就把數量 $-1$，最後就可以知道有幾個宗教
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[50005] ; // A 併查集
int num ; // 團體(宗教)數量
int find_root(int x) { // 查找團長
while (x != A[x]) {
A[x] = A[A[x]] ;
x = A[x] ;
}
return x ;
}
void merge_tree(int x, int y) { // 合併團體(宗教)
int fx = find_root(x), fy = find_root(y) ;
if (fx == fy) return ; // 同團體(宗教)
num-- ; // 合併後團體-1(宗教-1)
if (fx > fy)
A[fx] = fy ; // 更新團長
else
A[fy] = fx ; // 更新團長
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, a, b, times = 1 ;
while (cin >> n >> m) {
if (n == 0) break ; // 輸入結束
num = n ;
for (int i=0;i<n;i++) // 初始化
A[i] = i ;
for (int i=0;i<m;i++) {
cin >> a >> b ;
merge_tree(a, b) ; // 合併團體
}
cout << "Case " << times << ": " << num << '\n' ;
// 有多少團體(宗教)
times++ ;
}
return 0 ;
}
```
## a445. 新手訓練系列- 我的朋友很少
[題目連結](https://zerojudge.tw/ShowProblem?problemid=a445)
朋友的朋友就是我的朋友，也可以說朋友關係是邊，每個人都是點
所以兩個人是朋友也就是兩個點連通，所以可以用 DFS/BFS 去找，但是**速度很慢**
所以用並查集+路徑壓縮就可以快速解決，因為**兩點連通**也就是兩點在**同一棵樹**上
也就是同根，同根就是同並查集，不同根就是不同樹，也就是不同並查集
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[10005] ; // A 併查集
int find_root(int x) { // 查找團長
return x == A[x] ? x : A[x] = find_root(A[x]) ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, q, a, b ;
cin >> n >> m >> q ;
for (int i=1;i<=n;i++) // 初始化
A[i] = i ;
for (int i=0;i<m;i++) { // 合併
cin >> a >> b ;
int ra = find_root(a), rb = find_root(b) ;
A[ra] = rb ;
}
for (int i=0;i<q;i++) { // 查詢
cin >> a >> b ;
int ra = find_root(a), rb = find_root(b) ;
if (ra == rb) // 同團體
cout << ":)\n" ;
else // 不同團體
cout << ":(\n" ;
}
return 0 ;
}
```
## f292. 11987 - Almost Union-Find
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f292)
這題就很有趣了，除了合併之外，還需要實現兩個操作，會用圖幫助各位理解
1. 刪除某個團員 $P$ 並將它加入 $Q$ 所在的群體
2. 印出 $P$ 所在群體包含的成員個數和成員編號總和
在刪除點的時候，會出現兩個情況，一個是刪去根節點(圖 $1\rightarrow2$ )，一個是刪去其餘點(圖 $1\rightarrow3$ )
但是題目是刪去點 $P$ 後將其加入 $Q$ 所在的群體，所以不論刪除的點是不是根，都需要把樹接好
但要把樹接好，有兩種可能的行為
1. 如果是根，把根的所有子樹合併成一棵樹
2. 如果不是根，把其所有子節點的樹都接到父節點上
第一種可能的範例 : 把圖 $2$ 的 $3,4$ 接到點 $2$ 上面
第二種可能的範例 : 把圖 $3$ 的 $5,6$ 接到點 $1$ 上面
這時候如果想把第二種可能直接去除，也就是**拔掉所有根以外點的子節點**(圖 $4$ )
可能有人看出來了，這不就是**遞迴路徑壓縮**嗎，路徑壓縮後不論去除點 $2\sim 5$ 都可以**直接去除**
但很明顯還有**根節點沒辦法處理**，所以這裡提供一個想法，就是**虛構根**
先假設一個點 $A$ 是樹根，那不論點 $1\sim6$ 都可以**直接去除**了，只要確保 A 在**題目範圍外**即可
接著來說"成員編號總和"的計算方法，因為成員人數跟編號總和都可以在**合併的時候**讀取陣列
公式 : `新團體成員編號總和 = 舊團體(1)成員編號總和 + 舊團體(2)成員編號總和`
所以跟團體人數一樣可以用一維陣列儲存
還有題目當中幾個小細節也講講
因為一開始所有人都是**自己一組**，所以成員編號總和就是自己，成員人數是 $1$
虛構根可以用 $i+n$ 的方式去儲存，因為 $i+n$ 的點**一定不會用到(範圍外)**，正好能當虛構根
最後把整個流程都整理一遍
1. 初始化並查集(需有虛構根)、成員人數跟成員編號總和
2. 開始執行操作
3. 如果遇到 $1$，合併兩團體
4. 如果遇到 $2$，去除 $P$，把 $P$ 放進 $Q$ 所在的團體中
5. 如果遇到 $3$，讀取陣列輸出團體人數跟成員編號總和
在點 $4$ 當中，假設 $P$ 原本的團長是 $X$，$Q$ 的團長是 $Y$、成員人數是 $S$、成員編號總和是 $T$
那去除 $P$，$S_X-1,\ T_X-P$ 且 $S_Y+1,\ T_Y+P$
點 $3$ 的數值變動剛剛說過了，所以就不贅述
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
int A[200005], S[200005] ; // A 併查集、S 團體數量、
LL T[200005] ; // T 團體的編號總和(用 long long int)
int find_root(int x) { // 查找團長
return x == A[x] ? x : A[x] = find_root(A[x]) ;
}
void merge_tree(int x, int y) { // 合併團體
A[x] = y ; // 合併團體
S[y] = S[y] + S[x] ; // 更新團體人數
T[y] += T[x] ; // 更新團體編號
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, a, p, q ;
while (cin >> n >> m) {
for (int i=0;i<=n;i++) { // 初始化
A[i] = A[i+n] = i+n ; // 建立虛構根(不會被刪除的根)
S[i] = S[i+n] = 1 ;
T[i] = T[i+n] = i ;
}
for (int i=0;i<m;i++) {
cin >> a ;
if (a == 1) { // 合併
cin >> p >> q ;
int fp = find_root(p), fq = find_root(q) ;
if (fp == fq) continue ; // 同團體(跳過合併)
merge_tree(fp, fq) ; // 合併
}
else if (a == 2) { // 去除跟合併
cin >> p >> q ;
int fp = find_root(p), fq = find_root(q) ;
if (fp == fq) continue ; // 同團體(跳過去除)
A[p] = fq ; // p 進入 q 的團體
S[fp]--, S[fq]++ ; // 原團體人數-1、q 的團體人數+1
T[fp] -= p ; // p 的原團體編號 -p
T[fq] += p ; // q 的團體編號 +p
}
else { // 輸出
cin >> p ;
int fp = find_root(p) ;
cout << S[fp] << ' ' << T[fp] << '\n' ;
}
}
}
return 0 ;
}
```
## f310. 10158 - War
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f310)
這題很有趣，因為除了**操作**之外還有很多**性質**需要照顧到，為了方便先列出來
1. 朋友的朋友也是朋友(與自身同一集合)
2. 敵人的敵人也是朋友(與自身同一集合)
3. 朋友的敵人也是敵人(與自身敵人同一集合)
4. 朋友是互相的(我把你當朋友代表你也把我當朋友)
5. 敵人是互相的(我把你當敵人代表你也把我當敵人)
6. 自己跟自己一定是朋友
7. 自己跟自己一定不是敵人
這七個特性**背後的概念**我都寫在括號裡面了，操作還要注意不能成為**矛盾關係**，最後總結成
"如果已經是朋友，就不能是敵人，反之亦然"，假設兩個團長為 $A,B$，他們的敵人是 $A^\ast,B^\ast$
上面兩張圖(箭頭兩端是**朋友**關係、有權重 $1$ 的邊是**敵對**關係、箭頭指向**團長**)
$2、0$ 想當朋友，因為特性 $3$，所以 $4$ 會變成 $0$ 的敵對團體成員，$3$ 也會變成 $0$ 的敵對團體成員
也就是說，$3、4$ 會變成同一組的，$0、1、2$ 是同一組的，兩組成敵對關係
也可以直接把團體關係統整成團長之間的關係，$0$ 跟 $3$ 是敵對關係
但在實際的程式碼當中，反而會用 $A,A^*$ 表示敵對的兩個團體(團長)
上面兩張圖(箭頭兩端是**朋友**關係、有權重 $1$ 的邊是**敵對**關係、箭頭指向**團長**)
$0、3$ 要變成敵人，因為特性 $2$，所以 $4$ 會變成 $3$ 的朋友
也就是說，$3、4$ 會變成同一組的，$0、1、2$ 是同一組的，兩組成敵對關係
也可以直接把團體關係統整成團長之間的關係，$0$ 跟 $3$ 是敵對關係
所以在操作前要先判斷**兩者與其敵對團體**的關係，我在下面總結一下
---
交朋友前要先注意，如果對方是**敵人的朋友**，或自己是**對方敵人的朋友**
那都不可以成立(也就是矛盾情況)，如果都不是，就可以結交朋友
但結交朋友還要注意第 $3$ 點特性，$A$ 跟 $B$ 當朋友，就是 $A^*$ 跟 $B^*$ 當朋友
---
當敵人前要先注意，如果對方是**朋友**，或自己敵人是**對方敵人的朋友**
那都不可以成立(也就是矛盾情況)，如果都不是，就可以當敵人
但當敵人還要注意第 $4$ 點特性，$A$ 變成 $B^*$，同時 $B$ 變成 $A^*$
從這上述可以看出來我們除了要記錄**誰跟誰是朋友**外，還需要記錄**誰跟誰是敵人**
一樣可以用虛構根，用 $i+n$ 的方式代表 $i$ 的敵人集合，所以最後可以用下面程式碼表示
```cpp=
A[i] = x // x 是 i 的團長
A[1+n] = 2+n // 1 敵人那團的團長是 2 的敵人
```
如果用圖片解釋的話，那這張圖假設有 $10$ 個人，這是其中兩個團體的關係
那 $A[0] = A[1] = A[2] = 0$，但 $A[2+n] = A[2+10] = 2 \not= 4$
因為剛剛說過 $A[i+n] = i+n$ 意思是 $i+n$ 為 $i$ 敵對團團長，所以它也算是一種**虛擬根**
因為一開始我們其實不確定 $i$ 的敵人是誰，但我們確定 $i$ 有一個朋友(他自己)
所以從左邊變成右邊的圖時，雖然 $3,4$ 當中是 $3$ 當團長，但是它在程式碼當中是 $0+n = 0+10$
最後提醒幾個小細節
1. 要輸入關係直到輸入到 $0\ 0\ 0$
2. 兩團體有三種可能關係 : 朋友、敵人、沒關係
根據第二個細節，不可以用"不是朋友就是敵人"去寫邏輯判斷，而是要用上面說的邏輯去解
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int A[20005]; // F 朋友(10000)、O 敵人(10000)
int find_r(int x) { // 查找團長
return x == A[x] ? x : A[x] = find_r(A[x]) ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, c, x, y ;
cin >> n ;
for (int i=0;i<n;i++)
A[i] = i, A[i+n] = i+n ;
while (cin >> c >> x >> y) {
if (!(c || x || y)) break ; // 0 0 0
int Fx = find_r(x), Fy = find_r(y), Ox = find_r(x+n), Oy = find_r(y+n) ;
// x 所在團的團長、y 所在團的團長、x 敵人團的團長、y 敵人團的團長
if (c == 1) { // x, y 想交朋友
if (Fx == Oy || Fy == Ox)
cout << "-1\n" ; // x 跟 y 的敵人同團、y 跟 x 的敵人同團
else {
A[Fx] = Fy ; // 根據特性合併
A[Ox] = Oy ;
}
}
else if (c == 2) { // x, y 想變敵人
if (Fx == Fy || Ox == Oy)
cout << "-1\n" ; // x 跟 y 同團、x 的敵人跟 y 的敵人同團
else {
A[Fx] = Oy ; // 根據特性合併
A[Ox] = Fy ;
}
}
else if (c == 3) { // x, y 是朋友嗎
if (Fx == Fy || Ox == Oy)
cout << "1\n" ;
else
cout << "0\n" ;
}
else if (c == 4) { // x, y 是敵人嗎
if (Fx == Oy || Fy == Ox)
cout << "1\n" ;
else
cout << "0\n" ;
}
}
return 0 ;
}
```
## 刪除併查集
給定一張圖，圖上有 $n$ 個點，每次都要刪除一點與其相連的邊，共刪除 $m$ 次，問剩餘連通塊數量
基本上我們不太可能刪除併查集，要不然就是要使用之前說過的虛擬根技巧
不過這類型的題目，通常都是能夠反向來做的，因為給了圖也給刪除的點
所以可以改成給定一張圖與多個點(沒被刪除的)，問連通塊數量
我會用 $-1$ 代表被刪除的點，只要遇到 $-1$ 就跳過不合併
這題太簡單，只是要提醒反向思考而已，所以就不附程式碼
(如果真的需要可以找我要，但我沒有 judge 的題目)
## 基於併查集的最小生成樹-Kruskal
併查集還能建構最小生成樹，基本原理就是透過併查集去找未進入樹的點
而由於最小生成需要總權重最小，所以還要把所有邊先排序過一遍
然後依照排序後的邊去合併兩個不同併查集的點
```cpp=
#include<bits/stdc++.h>
using namespace std ;
struct p {
int w, n1, n2 ;
};
bool cmp(p p1, p p2) {
return p1.w < p2.w ;
}
int A[10005] ;
int find_root(int x) {
while (x != A[x])
x = A[x] = A[A[x]] ;
return x ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m ;
cin >> n >> m ; // 圖有 n 個節點、m 條邊
vector<p> E(m) ; // 共裝 m 個邊
for (int i=1;i<=n;i++)
A[i] = i ;
for (int i=0;i<m;i++)
cin >> E[i].w >> E[i].n1 >> E[i].n2 ; // 權重、兩點
int total = 0 ;
sort(E.begin(), E.end(), cmp) ;
for (int i=0;i<m;i++) {
int r1 = find_root(E[i].n1), r2 = find_root(E[i].n2) ;
if (r1 == r2)
continue ;
total += E[i].w ; // 更新權重總和
A[r1] = A[r2] = min(A[r1], A[r2]) ; // 合併
}
cout << total ; // 輸出總和
return 0 ;
}
```
至於證明方法我個人認為可以先更進一步地去了解生成樹之間的關係
而不是去硬吃演算法的證明，先跳過沒關係
這個部分也只是補充併查集的應用
## 額外補充題目(無 judge、未更新、難度高)
給一張權重無向圖，你要自定義每個點是白色或是黑色
在各種不同的可能情況中，假設整張圖中同色節點間的權重最大為 $X$
求最小 $X$ 對應的圖
這題會有兩種情況，第一種是同色點之間權重為 0，比如說一條鏈狀的圖
第二種情況比較多見，也就是同色點之間權重 > 0，比如說一個三角形
實際的運算其實也是遵守一個原則，就是先把大的處理掉
因為如果在定義節點顏色的過程中，能夠讓權重大的邊盡量變成第一種情況(不同色)
就可以讓權重小的邊處在同色的情況
比如這張圖使用了一個方法，我們先忽略題目說的權重部分去理解會比較快
圖上兩點之間的權重是 0 跟 1，其實不是真正的權重而是代表某邊接的兩個點顏色差異
1 代表兩個不同色，0 代表兩個同色，所以圖中 1 跟 3 是同色的但跟 2 不同色
這樣的好處是我們能透過前面的邊推斷出下一個邊權重是什麼
比如現在只有兩個邊，一樣是上面的圖，假設只有 12 跟 23 兩個邊
那 1 跟 3 就一定是不一樣的顏色，如果這時新增一個 13 呢
因為 12、23 都出來了所以我們可以推測出 13 就是 0
(之後只要找點到樹根的同異色就能判斷兩點同異色)
(依舊可以做路徑優化)
Sign in with Wallet
Connect another wallet