P3367 【模板】并查集

并查集算法

定义

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

来自百度百科。

样例分析

以样例为例，现有四个元素如下图所示。

第一个询问 2 1 2 显然它们不在一个集合之中，故输出 N 。

第二个操作 1 1 2 即将点一所在的集合与点二所在的集合合并。

显然，这个时候再询问一次 2 1 2 点一与点二就在同一个集合中了，故输出 Y 。

具体实现

我们就可以发现，如果将同一个集合的所有点表示为一个图，那么它们都是可以互相到达的，以此类推，同一个集合内的两个点都可以到达集合中的某个点，我们就设其中的任意一个固定的点为“代表元素”。所以，我们可以使用

a_i

表示第

i

个元素所在集合的代表元素，如果

a_i=a_j

那么第

i

个元素与第

j

个元素就在同一个集合里。

路径压缩优化

可以发现，我们很难选定一个元素为代表元素，查找的时候会花费大量时间，于是就有了路径压缩。

本意就是将集合中的每一个元素都一致地指向该集合中的一个元素，以下就是并查集路径压缩的核心算法。

CPP

int find (int now){return a[now]==now?now:a[now]=find(a[now]);}

AC代码

理解了算法之后，输入输出就没有难度了。

CPP

#include <bits/stdc++.h>
using namespace std;
int a[10000005];
int find (int now){return a[now]==now?now:a[now]=find(a[now]);}
void add(int x,int y){a[find(x)]=find(y);}
int main(){
	int n,m,z,x,y;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		a[i]=i;
	}
	for(int i=0;i<m;i++){
		cin>>z>>x>>y;
		if(z==1){
			add(x,y);
		}else{
			find(x)==find(y)?cout<<'Y'<<endl:cout<<'N'<<endl; 
		}
	}
	return 0;
}

题解：P3367 【模板】并查集

文章操作