连通性算法

 

1-1.快速查找（通过标记有联系对象，在数组中的值相同）
/*********快速查找********/
#include<stdio.h>
#define N 1000
main()
{
 int i,p,q,t,id[N];
 for(i=0;i<N;i++)
 id[i]=i;

 while(scanf(%d %d\n",&p,&q) == 2)
 {
 if(id[p] == id[q])
  continue;
 for(t=id[p],i=0;i
  if(id[i] == t)
   id[i]=id[q];
 printf("%d %d\n",p,q);
 }
}

1-2.快速并集算法（通过修改数组值，从而构建一颗一般的树来记录：各对象的连通性）
/*********快速并集********/
#define N 1000
main()
{
 int i,p,q,id[N];
 for(i=0;i
 id[i]=i;

 while(scanf(%d %d\n",&p,&q) == 2)
 {
 for(i=p;i!=id[i];i=id[i]);
 for(j=q;j!=id[j];j=id[j]);
 if(i==j)
  continue;
 id[i]=j;
 printf("%d %d\n",p,q);
 }
}

1-3.快速并集加权算法（在快速并集加权算法上对生成树进行压平处理，以减少搜索路径）
/*********快速并集加权********/
#define N 1000
main()
{
 int i,p,q,id[N],sz[N];
 for(i=0;i<N;i++)
 {
 id[i]=i;
 sz[i]=1;
 }
 while(scanf(%d %d\n",&p,&q) == 2)
 {
 for(i=p;i!=id[i];i=id[i]);
 for(j=q;j!=id[j];j=id[j]);
 if(i==j)
  continue;
 if(sz[i] < sz[j])
  {
   id[i]=j;
   sz[j]+=sz[i];
  }
 else
  {
   id[j]=i;
   sz[i]+=sz[j];
  }
 printf("%d %d\n",p,q);
 }
}

1-4.快速并集加权对分路径压缩算法。
/*********快速并集加权对分路径压缩********/
#define N 1000
main()
{
 int i,p,q,id[N],sz[N];
 for(i=0;i
 {
 id[i]=i;
 sz[i]=1;
 }
 while(scanf(%d %d\n",&p,&q) == 2)
 {
 for(i=p;i!=id[i];i=id[i])
  id[i]=id[id[i]];
 for(j=q;j!=id[j];j=id[j])
  id[j]=id[id[j]];
 printf("%d %d\n",p,q);
 }
}