# Disjoint-Set Union (並查集)

### 介紹
併查集（英文：Disjoint-set data structure，直譯為不交集資料結構）是一種資料結構，用於處理一些不交集（Disjoint sets，一系列沒有重複元素的集合）的合併及查詢問題。併查集支援如下操作：

1. 查詢：查詢某個元素屬於哪個集合，通常是返回集合內的一個「代表元素」。這個操作是為了判斷兩個元素是否在同一個集合之中。
2. 合併：將兩個集合合併為一個。
3. 添加：添加一個新集合，其中有一個新元素。添加操作不如查詢和合併操作重要，常常被忽略。

我們用一張圖來看


假設這些網路線將這些電腦分成了三個獨立的群組
我想要知道
「A與C相通嗎?」
(連接A與B)
(連接B與C)
「那此時A與C相通嗎?」

你可能想說就只要依照詢問的點做dfs就好，但是效率並不怎麼好，如果遇到幾十萬幾百萬的點，就很難處理。 尤其空間上的消耗很大。

### 此時我們先引入一個簡單但沒有效率的概念

## 概念

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

如果此時連接1和5，那就把5號電腦那格改成1號。

在連接2和7，就把7號改成2號

詢問7號和1號相通嗎? 答案是並不相通，因為1號屬於1號群組，7號屬於2號群組
如果我們在連接2和5 請注意：因為7也和2同一組，因此我們要把2和7都改成1號群組

在詢問一次7號和1號相通嗎？ 這時因為7號和1號都屬於1號群組，所以是相通的。

雖然作法簡單，但看出問題所在了嗎？ 我們在每次改動會耗上很多時間，尤其當其一群組擴大的時候像是

如果要連接1號和2號，那麼就要把2號至100萬號都改成1號群組，這樣就要改999999次了。 此時我們只要轉個小定義，就可以省下很多時間了。

原本我們剛剛的看法是「這台電腦屬於幾號群組」
現在我們轉成「這台電腦的老大是哪台電腦，他在哪就代表我在哪」

以上述的例子來看，要詢問5號和3號有沒有連接，5號的老大是2號，3號的老大也是2號。
連接1號和2號，我們會更改2號的老大為1號，此時在詢問5號和3號有沒有連接
5號的老大是2號，2號的老大是1號
3號的老大是2號，2號的老大是1號，所以就可以判定是相通的。 這樣一來，其他阿貓阿狗的號碼是誰都不重要了。

## Disjoint-Set Union (DSU)
此想法最重要的概念有兩個，合併(Union)與查詢(Find)。 其實還有一個是添加，但不如合併與查詢重要。

1. 添加 (初始化)
- 對於添加的點，因為還沒有任何連接，所以要先設定自己是自己的老大。

    for(int i = 0 ; i <= n; i++) boss[i] = i;

2. 查詢 (找源頭)
- 也就是剛剛說的找老大。找到源頭後，並且更改自己的老大，和簡單想法不同的在於，不用每個群組的人都改老大，有用到在去找源頭。

    int find_root(int x)
    {
        if(boss[x]==x) return x; //如果他自己就是他那群的源頭，就回報他自己的編號

        int root=find_root(boss[x]); //找出他老大的源頭
        boss[x]=root; //把他的boss也改成終極boss(源頭)的編號
        return root;
    }

3. 合併 (連接)
- 要連接他們的話，我們要先把他們個別的源頭找出來，並且讓其中一個源頭「歸順」到另一個源頭

    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(void){
    char qus;
    int n, a, b;
    cin >> n; //有n個點
    for (int i = 0 ; i < n ; i++) boss[i] = i; //初始化
    
    while(cin >> qus){      
        cin >> a >> b;
        if (qus == 'c') { //連接ab
            connect(a,b); 
        } else if (find_root(a) == find_root(b)) { //判斷ab是否相通
            cout << "a and b connect" << '\n';
        } else {
            cout << "a and b not conncect" << '\n';
        }
    }
}

<!-- ## 完整程式碼

#include <bits/stdc++.h>
using namespace std;

int target[10000000] ;

int find_root(int x){
    if(target[x] == x) return x;
    
    int root = find_root(target[x]);
    target[x] = root;
    return root;
}

void connect(int x,int y){
    int root_x = find_root(x);
    int root_y = find_root(y);
    target[root_x] = root_y;
}
int main(void){
    //ios::sync_with_stdio(false),cin.tie(0);
    int all, a, b, n;
    string ch;
    char q;
    cin >> all;
    while(all--){
        cin >> n;
        getchar();
        for(int i = 0 ; i <= n; i++) target[i] = i;
        int yes = 0 ,no = 0;
        while( getline(cin, ch) && ch != ""){
            stringstream ss(ch);
            ss >> q >> a >> b; // q 是 連結或詢問 a 點 b點
            if(q == 'c'){
                connect(a,b);
            }else{
                if ( find_root(a) == find_root(b) ){
                    yes++;
                }else {
                    no++;
                }
            }
        }
        cout << yes << ',' << no << '\n';
        if(all >= 1) cout << '\n';
    }
}

###### tags: `演算法`
{%hackmd aPqG0f7uS3CSdeXvHSYQKQ %}