并查集

筆試、面試、競賽非常喜歡問的一種算法。

用一個數(shù)組來維護每個集合

作用：

1、將兩個集合合并

2、詢問兩個元素是否在一個集合當中

而使用并查集可以在近乎的時間復雜度完成這兩個操作

思想：

每一個集合使用樹的思想來維護，每一個集合通過根節(jié)點來辨識；每個點都有一個指向父節(jié)點的指針，通過不斷向上找祖宗就能知道當前元素屬于哪個集合

image-20220226193042112

并查集的路徑壓縮優(yōu)化：

一旦第一次找到根節(jié)點，后面會把 這個路徑上的所有節(jié)點都指向根節(jié)點，使得后面若是找根節(jié)點所有節(jié)點只需一步操作。優(yōu)化之后的時間復雜度就是

// 最基礎的并查集例題
#include <iostream>
using namespace std;
const int N = 10e5+10;

int p[N]; // 現(xiàn)將n個祖宗節(jié)點放到p數(shù)組中
int n,m;
int find(int x){   // 返回的是祖宗節(jié)點
    if(p[x] != x)  p[x] = find(p[x]);  // 這個并查集直接用了壓縮路徑法優(yōu)化
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    // 1. 先把1-n分別讀入祖宗數(shù)組
    for(int i = 1; i<=n;i++){
        p[i] = i;
    }    
    char op;
    while(m--){   
        int a,b;
        scanf(" %c%d%d",&op,&a,&b);  // scanf讀char的時候會自動讀入空格、回車；但是讀入char[]字符串的時候，會自動忽略空格回車
        // 建議scanf讀字符串，這樣可以自動過濾空格回車
        
        // 如果想讀入char的話，scanf的時候" %c" 記得前面加一個空格即可()
        
        if(op == 'M'){
            // 2.合并集合
            p[find(a)] = find(b);     // 合并兩個集合
            // cout << "***"<<endl;
        }else if(op == 'Q'){
            // 3.詢問是否在一個集合中
            // cout << "!!!"<<endl;
            if(find(a) == find(b)){   // 判斷數(shù)字是不是在一個集合里
                cout << "Yes"<<endl;
            }else{
                cout << "No"<<endl;
            }
        }
    }   
    return 0;
}

在并查集兩個基礎功能的基礎上的額外信息

進階1：想要動態(tài)知道當前集合內(nèi)的元素個數(shù)

合理的引入額外變量就能知道額外信息（感覺像廢話hhh）

// 引入size數(shù)組記錄祖宗節(jié)點內(nèi)的元素個數(shù)
// 這個題仍然是并查集的板子題
#include <iostream>

using namespace std;

const int N = 10e5+5;

int f[N],si[N];
int n,m;

void init(){
    for(int i = 1; i<=n;i++){
        f[i] = i;
        si[i] = 1;
    }
}

// 找祖宗節(jié)點
int find(int x){
   if(f[x] != x) f[x] = find(f[x]); // 使用遞歸可以讓代碼寫的更簡潔,這是一步妙到姥姥家的代碼
   return f[x];
}

void isSameBlock(int a,int b){
    if(find(a) == find(b)) puts("Yes");
    else puts("No");
}

int getNumofPoint(int a){
    return si[find(a)];
}

void connect(int a,int b){
    
    si[find(a)] += si[find(b)];  // 將b祖宗節(jié)點對應的si數(shù)值加到a祖宗節(jié)點對應的數(shù)值里面
    f[find(b)] = find(a);        // 注意此時的祖宗是a 
    // cout << find(a) << " " <<find(b)<< endl;
}

int main(){
    cin >> n >> m;
    char op[3];
    
    init();
    while(m--){
        int a,b;
        scanf("%s%d%d",&op,&a,&b);
        if(op[0] == 'C'){
            if(find(a) == find(b)) continue;  // 如果在一個集合中了，跳過    // bug就是在這里
            connect(a,b);
        }else if(op[0] == 'Q'){
            if(op[1] == '1'){
                isSameBlock(a,b);
            }else if(op[1] == '2'){
                cout << getNumofPoint(a) << endl;
            }
        }
    }
    return 0;   
}