嘿大家，我又回來了，今天我們來介紹一下并查集，它是一種很高效的演算法，值得學習

引入

洛谷P3367

如題，現在有一個并查集，你需要完成合并和查詢操作，

輸入輸出格式

輸入格式：
第一行包含兩個整數N、M，表示共有N個元素和M個操作，

接下來M行，每行包含三個整數Zi、Xi、Yi

當Zi=1時，將Xi與Yi所在的集合合并

當Zi=2時，輸出Xi與Yi是否在同一集合內，是的話輸出Y；否則話輸出N

輸出格式：
如上，對于每一個Zi=2的操作，都有一行輸出，每行包含一個大寫字母，為Y或者N

輸入輸出樣例

輸入樣例#1：
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
輸出樣例#1：
N
Y
N
Y
說明

時空限制：1000ms,128M

資料規模：

對于30%的資料，N<=10，M<=20；

對于70%的資料，N<=100，M<=1000；

對于100%的資料，N<=10000，M<=200000，

一、思考

看完題目，你可能一頭霧水，也可能靈光乍現，我們就先來了解一下什么是并查集：

并查集被很多OIer認為是最簡潔而優雅的資料結構之一，主要用于解決一些元素分組的問題，它管理一系列不相交的集合，并支持兩種操作：

合并（Union）：把兩個不相交的集合合并為一個集合，
查詢（Find）：查詢兩個元素是否在同一個集合中，

是的，我們可以把并查集理解成是一種集合資料庫，里面記錄了集合之間的關系，這樣說未免讓人摸不著頭，我們就先來引入一個實際問題

現在有5個人，名叫1，2，3，4，5，他們有各自的老大（老大可以是自己），現在規定，1，2，3共用一個老大，4，5共用一個老大（或者說是共用一個組），我們可以如何表示呢？

是的，我們當然可以把1，2，3存入一個陣列叫a，把4，5存入一個陣列叫b，但這樣未免慢了些，有什么快捷的方法嗎？有的，并查集

我們先設定一個陣列名叫p，如果要實作用一條陣列存盤這樣的關系，我們可以規定1，2，3的老大是1，4和5的老大是4，那么如果將p的下標定義為人員，內部存的資料定為它的老大，是不是就可以得到這個關系了呢？沒錯，得到的p就是[1，1，1，4，4]（下標從1到5），

我們執行查詢的時候，比如說我要知道3的老大是誰，我只需要呼叫p[3]，里面存的就是集合頭子，

好的，現在我們已經介紹了查詢了，如何合并呢？聰明的你一定想到了，如果我要合并上述第一個和第二個集合，我只需要把第二個集合的內容都改成第一個的頭子即可，

二、具體實作

這里find()函式我們要單獨拎出來講講：

int f[10005];
int find(int k){
    return f[k]==k?k:f[k] = find(f[k]);
}

我們注意到find是這樣運作的：
1.如果找到的f陣列內容就是本身查詢的k值（自己就是自己的頭子，相當于上述例子p[1]=1），則直接回傳k值
2.如果不是，就要去更深層挖掘，也就是我們寫的遞回程式，令f[k] = find(f[k])，一方面在尋找k的總頭子（頭子也可能有頭子），一方面也直接把找到的值賦給了f[k]，我們管這叫路徑壓縮
（路徑壓縮優化后，并查集的時間復雜度已經比較低了，絕大多數不相交集合的合并查詢問題都能夠解決）

代碼如下（示例）：

#include<bits/stdc++.h>
using namespace std;
int f[10005];
int find(int k){
    if(f[k]==k)return k;
    else return f[k] = find(f[k]);
    
}
int main(){
     int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)f[i] = i;
    int type,a,b;
    while(m--)
    {
        scanf("%d%d%d",&type,&a,&b);
        if(type==1){
            f[find(b)] = find(a);
        }else
        {
                if(find(b)==find(a))
                cout << "Y" << endl;
            else
                cout << "N" << endl;
        }
        
    }
    
    
    
    return 0;
}

三、拓展題

ZCMU-1435
盟國
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 592 Solved: 143
世界上存在著N個國家，簡單起見，編號從0~N-1，假如a國和b國是盟國，b國和c國是盟國，那么a國和c國也是盟國，另外每個國家都有權宣布退盟（注意，退盟后還可以再結盟），

定義下面兩個操作：

“M X Y” ：X國和Y國結盟 (如果X與Z結盟,Y與Z結盟,那么X與Y也自動結盟).

“S X” ：X國宣布退盟 (如果X與Z結盟,Y與Z結盟,Z退盟,那么X與Y還是聯盟).

Input
多組case，

每組case輸入一個N和M (1 ≤ N ≤ 100000 , 1 ≤ M ≤ 1000000),N是國家數，M是運算元，

接下來輸入M行操作

當N=0，M=0時，結束輸入

Output
對每組case輸出最終有多少個聯盟(如果一個國家不與任何國家聯盟,它也算一個獨立的聯盟)，格式見樣例，

Sample Input

5 6
M 0 1
M 1 2
M 1 3
S 1
M 1 2
S 3
3 1
M 1 2
0 0

Sample Output

Case #1: 3
Case #2: 2

拓展題AC代碼

在這里我就先上代碼了，有能力的同學可以先看，看不懂的話下面我會解釋

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
int f[maxn],ff[maxn],vis[10000];
int find(int k){
    if(f[k]==k)return k;
    else return f[k] = find(f[k]);

}
int main(){
       int m,n,ca = 1;
    while(~scanf("%d%d",&n,&m))
    {
        int pos = n;
        if(m==0&&n==0)break;
        for(int i=0;i<maxn;i++)f[i] = ff[i] = i;
        while(m--){
            char str[2];
            int a,b;
            scanf("%s %d",str,&a);
            if(str[0]=='M'){
                scanf("%d",&b);
                int fa = find(ff[a]);
                int fb = find(ff[b]);
                if(fa!=fb)f[fa] = fb;
             }else if(str[0]=='S')
             {
                 ff[a] = pos;
                 f[pos] = pos;
                 pos++;
             }
        }
        set<int>s;
        for(int i=0;i<n;i++)
        s.insert(find(ff[i]));
        
        printf("Case #%d: %d\n",ca++,s.size());
        
    }
    return 0;
    }

思路講解

我們可以看到，現在這是一個關于數集合的樹，可以得到一個關系，2，3，4的老大是1，5和6的老大是4，如果我們現在要實作洗掉的操作，我們該怎么做呢？

洗掉操作比合并操作稍微復雜一點，
首先，我們已經用f陣列保存了原來結點間的關系（2，3，4的老大是1，5和6的老大是4），現在我們想要讓4從這個關系圖中剔除，我們就需要新建一個陣列ff[]，里面存盤的就是最新的關系

也就是說，洗掉操作要這樣執行

 ff[a] = pos;
 f[pos] = pos;
 pos++;
 //pos就是從n開始增大，因為題目資料范圍是0 to n-1

我們首先讓ff內的a指向pos，（pos已經在原有資料范圍之外了），我們可以理解為a這個資料被流放了，同時在f陣列執行f[pos] = pos，使得讓pos的老大就是本身，這樣在find運行時可以作為一個獨立的個體

我們用一個形象的比喻：
澳大利亞是英國殖民時期的罪犯流放地，但剛開始并沒有罪犯對吧，現在，英國本來有6個小混混，他們之間的關系如上圖，現在4號小混混（小頭子）放下了殺人罪，被法律規定要流放到澳大利亞，成為那里第一個犯人，于是，執行官（也就是ff陣列把ff[4]=7標記了）把4送到了7這個地方流放了，也就是新開辟的澳大利亞區域，但是，盡管4號小頭子被流放了，它兩個手下5和6的總頭子仍然是1，為了以后警察能通過f陣列仍然找到最大的頭子1，f陣列原來資料范圍內的資料是不會有變化的，只是會添加一條 f[pos] = pos，意味著如果澳大利亞警察找4的頭子，那還是會找到4本身的，

接下來講講稍微簡單的合并操作

int fa = find(ff[a]);
int fb = find(ff[b]);
if(fa!=fb)f[fa] = fb;

我們可以注意到，fa是在ff陣列（最新的犯罪記錄，用了上面的例子了）里用find函式查找a的頭子（注意：find函式用的還是f陣列，原因上面已經講過了），fb同理，如果頭子相同，那么不必執行操作，如果不同，就要在f陣列里面記錄a的頭子就是b的頭子（其實反過來也是對的）

總結

今天介紹了了并查集的簡單入門，查詢，合并和刪改，并做到了一些應用，后面那個例子講的可能不是非常恰當，但希望能幫助你理解，
如有出錯，希望在評論區告知，希望能給你們派上用場，