并查集

并查集

#include <bits/stdc++.h>
using namespace std;
const int maxn=9999999;
int pre[maxn],n;
int find(int x)//递归 
{
	//如果自己的上级不是自己，就去找到自己的最高级 
	if(pre[x]!=x)	pre[x]=find(pre[x]);
	return pre[x];
}
/*int find(int x)//循环
{
	int temp,p=x;
	while(x!=pre[x])//只要没到最高级
		x=pre[x];
	while(p!=x)//将沿途的节点的上一节点都设置为最高级 
	{
		temp=pre[p];//我们要修改成最高级，但要保存下当前值 
		pre[p]=x;
		p=temp;	
	}
	return x;		
} */
void join(int q,int w) 
{
	pre[find(q)]=find(w);//将q的最高级本来指向自己，现在令它指向w的最高级 
	return;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		pre[i]=i;//开始时父节点为自己 
	return 0;
}