并查集

关于并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。 ——《百度百科》

在并查集中主要有两个操作：合并和查找，其中查找需要用递归实现。

模板题

模板题：Luogu P3367 【模板】并查集

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int p[10005];
inline int read() {
	char ch=getchar();
	int s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+(ch-'0'); ch=getchar();}
	return s*w;//快读 
}
inline int find(int x){
	if(x==p[x]) return x;//如果x的上司是他自己， 那就是意味着x是老板 
	return p[x]=find(p[x]);//如果x的上司不是他自己，那就直接找出来x的老板，并且把x的老板直接作为x的上司（路径压缩） 
}
int main() {
	int n,m;
	n=read(),m=read();
	for(int i=0;i<=n;i++) p[i]=i;//初始化，每个人的老板都是自己
	while(m--){
		int x,y,z;
		z=read(),x=read(),y=read();
		int tx=find(x),ty=find(y);//tx代表x的老板，ty代表y的老板
		if(z==1){
			if(tx!=ty) p[tx]=ty;//合并操作：让y的老板成为x的老板的老板
		}
		if(z==2){
			tx==ty ? printf("Y\n") : printf("N\n");
		}
	}
	return 0;
}  

例题

洛谷P1551 亲戚 这也是一道很经典的例题，其实这种入门题核心思路基本一样，参考代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int p[100005];
int f(int x) {
	if(p[x]==x) return x;
	return p[x]=f(p[x]);
}
int main() {
	int n,m,z;
	scanf("%d%d%d",&n,&m,&z);
	for(int i=1; i<=n; i++) p[i]=i;
	while(m--) {
		int a,b;
		scanf("%d%d",&a,&b);
		int tx=f(a),ty=f(b);
		if(tx==ty) continue;
		p[tx]=ty;
	}
	while(z--) {
		int a,b;
		scanf("%d%d",&a,&b);
		int tx=f(a),ty=f(b);
		if(tx==ty) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}