# 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.找源頭
不管要查哪台電腦的源頭
我都可以透過不斷地「找到他的老大」、「找到他老大的源頭」來找到他的源頭

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.連接兩台電腦
這兩台電腦可能屬於不同的群組
因此有不同的源頭
要連接他們的話
我們要先把他們個別的源頭找出來
並且讓其中一個源頭「歸順」到另一個源頭

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的源頭 (若要反過來也可以)
}

最後就簡單啦

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的殼供你使用
你想自己寫的話也可以喔

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)