并查集模板--C语言

#include 

//初始化并查集
void Initial(int S[],int size){
	for(int i=0;i=0) root=S[root];//循环找到根
	while(x!=root){//压缩路径
	 	int t=S[x];//t指向x的父结点
		S[x]=root;//x直接挂到根节点下
		x=t; 
	} 
	return root;
} 
void Union(int S[],int Root1,int Root2){
	//找到两个结点的根节点
	Root1=Find(S,Root1);
	Root2=Find(S,Root2);
	if(Root1==Root2) return;//如果属于同一个集合那么不操作
	if(S[Root2]>=S[Root1]){//Root2结点数更少
		S[Root1]+=S[Root2];//累加结点总数 
		S[Root2]=Root1;//小数合并到大树
	}else{
		S[Root2]+=S[Root1];//累加结点总数 
		S[Root1]=Root2;//小树合并到大树 
	} 
}