AcWing 836. 合并集合
原题链接
简单
作者:
ζ孤
,
2021-05-23 12:55:53
,
所有人可见
,
阅读 234
用f[x] 存放x的父节点
当f[x] == x时表示x为根节点
判断树根
f[x] ?= x; `
合并两个集合
找到到每个集合中的根节点 :while(f[x] != x)x = f[x];
让一方的根节点为另一方根节点 f[x] = y 及合并到一颗树上
设函数find(x)是找到x的祖宗节点
合并就可以表示为:f[find(x)] = f[find(y)];
路径压缩:
可以看出合并时都要查询根节点加大了复杂度
可以在查询时,让 x到根节点路径上的顶点 都指向x根节点
while(x != f[x]) f[x] = find(f[x]); //find(x)返回x的祖宗节点
下次查询时就可以减少复杂度了
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int f[N];
int find(int x){
if(x != f[x])f[x] = find(f[x]);
return f[x];
}
int main()
{
cin >> n >> m;
for(int i = 1;i<=n;i++){
f[i] = i;
}
while(m -- ){
char c;
int x,y;
cin >> c >> x >> y;
if(c == 'M'){
f[find(x)] = f[find(y)];
}else {
if(find(x) == find(y))
cout << "Yes" << endl;
else
cout <<"No" << endl;
}
}
}