最简单的并查集题了吧！

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？  

本题只需将联通的村庄联系在一起而已！

#include<stdio.h>

int pre[1010];

int find(int k)

{

if(k==pre[k])

return k;

pre[k]=find(pre[k]);

return pre[k];

}

int main()

{

int n,m,i,a,b,f1,f2,ans;

while(scanf("%d",&n),n)

{

scanf("%d",&m);

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

pre[i]=i;

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

{

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

f1=find(a);

f2=find(b);

if(f1!=f2)

pre[f1]=f2;

}

ans=0;

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

if(i==pre[i])

ans++;

printf("%d\n",ans-1);

}

return 0;

}

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232

并查集：

 

定义

并查集是一种树型的 ，用于处理一些不相交 （Disjoint Sets）的合并及查询问题。常常在使用中以 来表示。

集就是让每个元素构成一个单元素的 ，也就是按一定顺序将属于同一组的 所在的集合合并。

 

 

 

初始化

把每个点所在 初始化为其自身。

通常来说，这个 在每次使用该 时只需要 一次，无论何种实现方式， 均为O(N)。

查找

查找元素所在的 ，即根节点。

合并

将两个元素所在的 合并为一个集合。

通常来说，合并之前，应先判断两个元素是否属于同一 ，这可用上面的“查找”操作实现。