并查集模版（C++）

#include
using namespace std;

const int N = 1e5;


int f[N];


//寻找根节点 
int find(int x){
	if(x != f[x]) f[x] = find(f[x]);
	return f[x];
}


//合并两个节点 
void Union(int a,int b){
	int pa = find(a);
	int pb = find(b);
	
	if(pa != pb){
		f[pa] = pb;
	}
	
	
}

//初始化 
void init(){
	for(int i=0;i<N;i++)
		f[i] = i;
}

int main(){
	init();//初始化后，每个节点的父节点就是本身，如：f[1] = 1 
	
	
	//1为根节点的集合 
	f[2] = 1;
	f[3] = 2;
	f[4] = 3;
	f[5] = 4;
	
	
	//6为根节点的集合 
	f[7] = 6; 
	f[8] = 7;
	
	
	//此时存在以1为根节点的集合，和以6为根节点的集合 
	
	
	
	
	
	//5的父节点是4，4的父节点是3，以此类推
	//到1的时候正好父节点和节点本身相等，那么1就是所有节点的根节点 
	cout<<find(1)<<endl;
	cout<<find(2)<<endl;
	cout<<find(3)<<endl;
	cout<<find(4)<<endl;
	cout<<find(5)<<endl;
	
	//和上面一样6是所有节点的根节点 
	cout<<find(7)<<endl;
	cout<<find(8)<<endl;
	

	
	return 0;
	
}