Ch21 並查集 - Disjoint Set

搭配 virtual judge解題系統

上一章：最短路徑 Dijkstra
回目錄：國立科學園區實驗中學C++程式語言自學講義

什麼是disjoint set

先來看看例題

有N台電腦
其中有一些網路線會將兩台電腦接在一起
如果A和B是連通的，且B和C是連通的
那麼A和C就會是連通的

這些網路線會將這些電腦分成一堆「互不相連」的路網
他們彼此之間就是「disjoint set」

如圖
這些網路線將這些電腦分成了三個獨立的群組

題目會一邊將兩台電腦接起來
一邊問你某兩台是不是連通的(是不是屬於同一個群組的)

例如，
題目input：
「A與C相通嗎?」
「連接A與B」
「連接B與C」
「A與C相通嗎?」

你的output：
「否」
「是」

因為題目可能會連一百萬條線
也可能會問一百萬次
因此要用很有效率的方法做才行

一個簡單但沒有效率的方法

用一個陣列紀錄「和那台電腦同一組的最小號碼」

假設每一個群組裡面最小號碼的那台電腦是組長

首先，還沒有任何網路線連接時
每一台電腦都是屬於自己的群組
也就是同組內的最小號碼都是自己

題目說：「連接1和5」

那就把5號電腦那格改成1號

題目說：「連接2和7」
那就把7號電腦那格改成2號

題目問：「7號和1號相通嗎?」
因為1號屬於1號群組
7號屬於2號群組
因此他們不相通，回答「否」

題目說：「連接2和5」
因為7也和2同一組
因此我們要把2和7都改成1號群組

題目問：「7號和5號相通嗎?」
因為7號和5號都屬於1號群組
可以判定他們相通，回答「是」

這個做法看似簡單
但其實在「改動」的過程會花上大把時間
例如

2號至100萬號都是2號群組的
這時候題目說「連接1號和2號」
那麼就要把2號至100萬號都改成1號群組
這樣就要改999999次了
如果題目故意出得讓你每次改動都要改這麼多次
你就會得到TLE

省時間的作法

在上述的案例中
題目說「連接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萬左右

復仇要冷冷端上

寫disjoint set的程式

概念聽起來很複雜
但程式寫起來很容易喔

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<<不相連
        }
    }  
}

【學生練習題】

• A - Network Connections
  有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; //最後一行不要換行(題目要求的)
    }
}

一個有趣的延伸思考題

敵人的敵人，就是朋友！
朋友的敵人，就是敵人！
敵人的朋友，也是敵人！

世界上有兩個幫派，龍幫與蛇幫
有N個人，每個人都屬於其中一個幫派

你不曉得每個人分別屬於哪個幫派
你只會陸續接到線索
知道某兩個人彼此是敵人(屬於不同幫派)

題目有M個指令
如果是D a b代表你現在知道a和b屬於不同幫派了
如果是A a b代表詢問a與b是否屬於同一個幫派
你的回答有三種：「相同」、「不同」、「不知道」

例如題目input說
「請問1和2的關係是?」
「發現1和2是敵人」
「請問1和2的關係是?」
「發現2和4是敵人」
「請問1和4的關係是?」

你的回答output會是
「不知道」
「敵人」
「朋友」

這題的做法和上一題非常類似
但為了處理「敵人」這層關係
需要多加一些步驟

【學生練習題】

• B - Find them, Catch them

上一章：最短路徑 Dijkstra
回目錄：國立科學園區實驗中學C++程式語言自學講義