并查集
笔试、面试、竞赛非常喜欢问的一种算法。
用一个数组来维护每个集合
作用：
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;
}
