并查集

笔试、面试、竞赛非常喜欢问的一种算法。

用一个数组来维护每个集合

作用：

1、将两个集合合并

2、询问两个元素是否在一个集合当中

而使用并查集可以在近乎的时间复杂度完成这两个操作

思想：

每一个集合使用树的思想来维护，每一个集合通过根节点来辨识；每个点都有一个指向父节点的指针，通过不断向上找祖宗就能知道当前元素属于哪个集合

image-20220226193042112

并查集的路径压缩优化：

一旦第一次找到根节点，后面会把 这个路径上的所有节点都指向根节点，使得后面若是找根节点所有节点只需一步操作。优化之后的时间复杂度就是

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

int p[N]; // 现将n个祖宗节点放到p数组中
int n,m;
int find(int x){   // 返回的是祖宗节点
    if(p[x] != x)  p[x] = find(p[x]);  // 这个并查集直接用了压缩路径法优化
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);
    // 1. 先把1-n分别读入祖宗数组
    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)){   // 判断数字是不是在一个集合里
                cout << "Yes"<<endl;
            }else{
                cout << "No"<<endl;
            }
        }
    }   
    return 0;
}

在并查集两个基础功能的基础上的额外信息

进阶1：想要动态知道当前集合内的元素个数

合理的引入额外变量就能知道额外信息（感觉像废话hhh）

// 引入size数组记录祖宗节点内的元素个数
// 这个题仍然是并查集的板子题
#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;
    }
}

// 找祖宗节点
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祖宗节点对应的si数值加到a祖宗节点对应的数值里面
    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;   
}