并查集:
1、将两个集合合并
2、询问两个元素是否在一个集合中
基本原理:
每个集合用一棵树来表示,树根的编号就是整个集合的编号,每个结点存储它的父节点,p[x]表示x的父节点
问题1:如何判断树根:if(p[x] == x)
问题2:如何求x的集合编号:while( p[x] != x) p = p[x];
问题3:如何合并两个集合:px是x的集合编号,py是y的集合编号:p[x]=y
涉及优化:路径压缩,讲每个点都指向他的祖宗节点
核心算法:
int find(int x){//返回x的祖宗结点 + 路径压缩
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
模板题836:
#include <iostream>
using namespace std;
const int N = 100010;
int n ,m;
int p[N];
int find(int x){//返回x的祖宗结点 + 路径压缩
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
cin >> n >> m;
for(int i = 0 ; i < n ; i++) p[i] = i;//初始化每个点指向自己
while(m--){
char op[2];
int a,b;
cin >> op >> a >> b;
if(op[0] == 'M') p[find(a)] = find(b);//合并,将a的祖宗结点连到b的祖宗结点下
else {
if(find(a) == find(b)) puts("YES");
else puts("NO");
}
}
return 0;
}