并查集总结

今天做的题目，我用关系闭包实现了，别人用的并查集，我又尝试了一下。

并查集就是把森林按某种关系合并即定义；

并查集的算法：

1,初始化森林，每棵树都只有一个点；

2,将有关系的点所在的树合并:如果两个树的名字相同就放回,因为已经是在一个树下了,如果不相同就把名字大的树的名字改成小的,（用数组表示树forast[顶点]==顶点所在的树此阶段在for循环中完成）；

时间复杂度应该是O(m*n);

例题（http://acm.hdu.edu.cn/showproblem.php?pid=1213）

#include<stdio.h>

int forast[1001];

int t,n,m;

int mytree(int point)//找顶点所在的树

{

return forast[point];

}

void merge(int a,int b)//合并

{

int temp,i,mintr,maxtr;

mintr=mytree(a);

maxtr=mytree(b);

if(mintr==maxtr)

return ;

if(mintr>maxtr){

temp=maxtr;

maxtr=mintr;

mintr=temp;

}

for(i=1;i<=n;i++)//将maxtr森林归并到mintr森林中,就是将两树合并（一个点一个点的合并）

if(maxtr==mytree(i))//如果i点的树==maxtr树就将他加入mintr中

forast[i]=mintr;

}

main()

{

int i,a,b,sum;

scanf("%d",&t);

while(t--){

scanf("%d%d",&n,&m);

for(i=1;i<=n;i++)////初始化森林,每个点各成树

forast[i]=i;

for(i=0;i<m;i++){

scanf("%d%d",&a,&b);

merge(a,b);//////合并a，b

}

sum=0;

for(i=1;i<=n;i++)

if(i==mytree(i))//数树的个数

sum++;

printf("%d/n",sum);

}

return 0;

}