# Ch21 並查集 - Disjoint Set
> 搭配 [virtual judge解題系統](https://vjudge.net/contest/277912)
##
> 上一章：[最短路徑 Dijkstra](https://hackmd.io/s/HJL8bMuxN)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
## <font color='darkblue'>什麼是disjoint set</font>
先來看看例題
有N台電腦
其中有一些網路線會將兩台電腦接在一起
如果A和B是連通的，且B和C是連通的
那麼A和C就會是連通的
這些網路線會將這些電腦分成一堆「互不相連」的路網
他們彼此之間就是「disjoint set」
如圖
這些網路線將這些電腦分成了三個獨立的群組
題目會一邊將兩台電腦接起來
一邊問你某兩台是不是連通的(是不是屬於同一個群組的)
例如，
題目input：
「A與C相通嗎?」
「連接A與B」
「連接B與C」
「A與C相通嗎?」
你的output：
「否」
「是」
因為題目可能會連一百萬條線
也可能會問一百萬次
因此要用很有效率的方法做才行
## <font color='darkblue'>一個簡單但沒有效率的方法</font>
用一個陣列紀錄「和那台電腦同一組的最小號碼」
假設每一個群組裡面最小號碼的那台電腦是組長
首先，還沒有任何網路線連接時
每一台電腦都是屬於自己的群組
也就是同組內的最小號碼都是自己
題目說：「連接1和5」
那就把5號電腦那格改成1號
題目說：「連接2和7」
那就把7號電腦那格改成2號
題目問：「7號和1號相通嗎?」
因為1號屬於1號群組
7號屬於2號群組
因此他們不相通，回答「否」
題目說：「連接2和5」
<font color='red'>因為7也和2同一組
因此我們要把2和7都改成1號群組</font>
題目問：「7號和5號相通嗎?」
因為7號和5號都屬於1號群組
可以判定他們相通，回答「是」
這個做法看似簡單
但其實在「改動」的過程會花上大把時間
例如
2號至100萬號都是2號群組的
這時候題目說「連接1號和2號」
那麼就要把2號至100萬號都改成1號群組
這樣就要改999999次了
如果題目故意出得讓你每次改動都要改這麼多次
你就會得到TLE
## <font color='darkblue'>省時間的作法</font>
在上述的案例中
題目說「連接1號和2號」之後
可能只會問「5號和777號相通嗎?」
其他電腦怎麼樣它根本不聞不問
那麼其他台電腦的號碼就白改了
又或是
在他連接完1號和2號，讓你把2至999999都改成1號群組時
又說了「連接0號和1號」
這時你又得把全部都改成0號群組
早知道剛才就不要把他們改成1號
直接等這次再改0號就好
這些被浪費掉的時間
其實我們都可以省下來
### 怎麼省下來呢
原本我們陣列格子裡存的是「這台電腦屬於幾號群組」
現在我們當成格子裡存的是「這台電腦的老大是哪台電腦，他在哪就代表我在哪」
例如剛才的問題
2號至999999號都把2號當老大
現在題目說「連接1號和2號」
我們只要把2號的格子改成1就好
代表「2號電腦把1號電腦當老大，1號電腦在哪，2號電腦就在哪」
這時題目若問說「5號電腦與777號電腦相通嗎?」
當我們看看5號格子時，看到了2，代表2號電腦是5號電腦的老大
再看看2號格子時，看到了1，代表1號電腦是2號電腦的老大，也就是5號電腦的老大
再看看1號格子時，看到了1，我們就知道找到5號的源頭老大是1號了
當我們看看777號格子時，看到了2，代表2號電腦是777號電腦的老大
再看看2號格子時，看到了1，代表1號電腦是2號電腦的老大，也就是777號電腦的老大
再看看1號格子時，看到了1，我們就知道找到777號的源頭老大是1號了
由於5號電腦和777號電腦的源頭老大都是1號
所以可以判定5號電腦和777號電腦是屬於同一個群組的
這樣一來
其他阿貓阿狗的號碼是誰都不重要了
我們就能把時間省下來
如果題目問的次數跟接線的次數保證在100萬次以內
我們就能保證程式在改格子或是找答案的總次數也在100萬左右
[復仇要冷冷端上](https://www.comico.com.tw/623/)
## <font color='darkblue'>寫disjoint set的程式</font>
概念聽起來很複雜
但程式寫起來很容易喔
1.找源頭
不管要查哪台電腦的源頭
我都可以透過不斷地「找到他的老大」、「找到他老大的源頭」來找到他的源頭
```cpp=
int find_root(int x)
{
if(boss[x]==x) return x; //如果他自己就是他那群的源頭，就回報他自己的編號
int root=find_root(boss[x]); //找出他老大的源頭
boss[x]=root; //把他的boss也改成終極boss(源頭)的編號
return root;
}
```
2.連接兩台電腦
這兩台電腦可能屬於不同的群組
因此有不同的源頭
要連接他們的話
我們要先把他們個別的源頭找出來
並且讓其中一個源頭「歸順」到另一個源頭
```cpp=
void connect(int x, int y)
{
int root_x=find_root(x); //找到x的源頭
int root_y=find_root(y); //找到y的源頭
boss[root_x]=root_y; //讓x的源頭歸順於y的源頭 (若要反過來也可以)
}
```
最後就簡單啦
```cpp=
int main()
{
for(int i=0;i<1000000;i++) boss[i]=i;//一開始大家的源頭都是自己
while(1)
{
cin>>指令
if(指令是連接a與b){
connect(a, b);
}
else if(指令是問a與b是否相連){
int root_a=find_head(a);
int root_b=find_head(b);
if(root_a==root_b) cout<<相連
else cout<<不相連
}
}
}
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [A - Network Connections](https://vjudge.net/contest/277912#problem/A)
> 有n台電腦，編號為1至n
> 接下來有若干個指令
> 指令為c a b代表連接a和b
> 指令為q a b代表詢問a與b是否相連
> 最後請輸出總共有幾次詢問是得到「相連」的答案
> 以及總共有幾次詢問是得到「不相連」的答案
這題的input有點麻煩
這裡提供一個main的殼供你使用
你想自己寫的話也可以喔
```cpp=
int main()
{
int Case, N;
cin>>Case;
while(Case--){
cin>>N;
//請在這裡用迴圈將大家的源頭都設定為自己
string input;
cin.ignore();
while(getline(cin, input)&&input!=""){
stringstream ss(input);
char t; //可能是c或q
int a, b;
ss>>t>>a>>b;
if(t=='c'){
//請連接a與b
}
else{
//請查詢a與b是否相通
}
}
//印出答案
if(Case>0) cout<<endl; //最後一行不要換行(題目要求的)
}
}
```
## <font color='darkblue'>一個有趣的延伸思考題</font>
敵人的敵人，就是朋友！
朋友的敵人，就是敵人！
敵人的朋友，也是敵人！
世界上有兩個幫派，龍幫與蛇幫
有N個人，每個人都屬於其中一個幫派
你不曉得每個人分別屬於哪個幫派
你只會陸續接到線索
知道某兩個人彼此是敵人(屬於不同幫派)
題目有M個指令
如果是D a b代表你現在知道a和b屬於不同幫派了
如果是A a b代表詢問a與b是否屬於同一個幫派
你的回答有三種：「相同」、「不同」、「不知道」
例如題目input說
「請問1和2的關係是?」
「發現1和2是敵人」
「請問1和2的關係是?」
「發現2和4是敵人」
「請問1和4的關係是?」
你的回答output會是
「不知道」
「敵人」
「朋友」
這題的做法和上一題非常類似
但為了處理「敵人」這層關係
需要多加一些步驟
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [B - Find them, Catch them](https://vjudge.net/contest/277912#problem/B)
##
> 上一章：[最短路徑 Dijkstra](https://hackmd.io/s/HJL8bMuxN)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet