并查集
1. 将两个集合合并
2. 查询两个元素是否在同一个集合
基本原理:
每个集合用一颗树表示,根结点的编号就是树的编号。
每个节点存储它的父节点,p[x]表示x的父节点
算法注意⚠️
1. 如何判断树根 p[x] == x
2. 如何求x的集合编号 while(x != p[x]) x = p[x]; — 路径压缩更新每一个节点的父节点(祖宗节点)
3. 如何合并两个集合 px,py分别是两个集合编号,p[px] = py
code1
#include<iostream>
using namespace std;
const int N = 100005;
int p[N];
int n, m;
int find(int x)
{
//返回x的祖宗节点 + 路径压缩
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b)
{
p[find(a)] = find(b);
}
bool query(int a, int b)
{
if(find(a) == find(b)) return true;
return false;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i){
// p指向自己时,表明是根结点
p[i] = i;
}
while(m --)
{
char op[2];
//scanf("%c"); 读单个字符时,容易读入奇怪的字符,比如空格,回车 *小技巧是读入字符串*
int a, b;
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'M'){
merge(a, b);
}
else {
if(query(a, b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}
code2: 连通块中点的数量
#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int p[N], cnt[N];
int n, m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) p[i] = i, cnt[i] = 1;
while(m --)
{
char op;
int a, b;
cin >> op;
if(op == 'C'){
cin >> a >> b;
//1 如果两个元素在同一个集合中,则不能合并
if(find(a) == find(b)) continue;
cnt[find(b)] += cnt[find(a)];
//2 main中一律用find(a) 而不是p[a] 这一步并没有及时更新原来a所在集合中元素
p[find(a)] = find(b);
}
else{
int t;
cin >> t;
if(t == 1) {
cin >> a >> b;
if(find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
else{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
}
return 0;
}