并查集.cpp

自己写的数据结构代码

#define N 10000
int parent[N];
void UFset()  //初始化
{
	for(int i=0;i<N;i++)
		parent[i]=-1;
}



int Find(int x)  //返回第Ｘ节点所属集合的根结点
{
	for(int i=x;parent[i]>=0;i=parent[i]);
	while(i!=x)   //优化方案――压缩路径
	{
		int tmp=parent[x];
		parent[x]=i;
		x=tmp;
	}
	return i;
}



void Union(int R1,int R2)  //将两个不同集合的元素进行合并，使两个集合中任两个元素都连通
{
	int tmp=parent[R1]+parent[R2];
	if(parent[R1]>parent[R2]) //优化方案――加权法则
	{
		parent[R1]=R2;
		parent[R2]=tmp;
	}
	else
	{
		parent[R2]=R1;
		parent[R1]=tmp;
	}
}

int kruskal(int parent[],int N)
{
	int i,j,k,x,y;
	int min;
	while(k<=N-1) //产生Ｎ－１条边
	{
		min=MAX_INT;
		for(i=1;i<=N;i++) 
			for(j=1;j<=N;j++)
			{
				if(sign[i][j]==0&&i!=j) //sign[N][N]是标志节点是否被访问过或已被排除……
				{
					if(arcs[i][j]<min)　//arcs[N][N]存放边的长度
					{
						min=arcs[i][j];
						x=i;
						y=j;
					}//if
				}//if
			}//for
			if(Find(parent,x)==Find(parent,y)) //如Ｘ，Ｙ已经属同一连通分量，则不合并，排除……
				sign[x][y]=1;
			else
			{
				Union(parent,x,y);
				Sign[x][y]=1;
			}
			k++;
	}//while
}