并查集模板

来自洛谷的板子

首先是find函数

int find(int k){
	if(f[k]==k) return k;
	return f[k]=find(f[k]);
}

找到每个集合的老大.

合并的操作

f[find(p2)]=find(p3);

然后判断不能只用数组判断，由于路径压缩的问题数组不能完全代表它的老大.

完整代码：

#include
#include
using namespace std;
int f[10010];
int find(int k){
	if(f[k]==k) return k;
	return f[k]=find(f[k]);
}

int main(){ int i,j,k,n,m,p1,p2,p3;
	cin>>n>>m;
	for(i=1;i