题目描述
某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？
输入格式
输入包含若干组测试测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 n 和道路数目 m ；随后的 m 行对应 m 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 1 到 n 编号。
注意：两个城市间可以有多条道路相通。
输出格式
对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。
输入输出样例
输入 #1
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
输出 #1
1
0
2
998
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int n=1,m;//n代表有多少个村庄，m是代表已有多少条路
int f[10000];//储存每个节点的“祖先”
void init()//预处理，一开始把每个结点的祖先设为自己
{
for(int i=1;i<=n;i++)f[i]=i;
//千万不能在输入前用此函数（n都没输入怎么预处理）
}
int find_(int x)//用到了路径压缩，比单纯的while更快
{
if(f[x]==x)//如果x的祖先是自己
retrun x;//那么返回x就好了。
return find_(f[x]);//如果不是的话，x的祖先的祖先就是x的祖先
}
void union_(int x,int y)//合并x,y两个结点
{
f[find_(y)]=find_(x);//让x的祖先成为y的祖先的祖先，这样y所在的集合里所有结点的祖先全变为x的祖先。
}
int main()
{
while(n!=0)
{
scanf("%d",&n);//输入n
if(n!=0)//判断n是否等于0
scanf("%d",&m);//是就输入m
else//否则就跳过
continue;
if(m==0)//如果m（路的条数）等于0的话，那么想必就没有路了
{
printf("%d
",n-1);//连起n个节点最少就要n-1条线
continue;
}
init();//预处理
int x,y;//定义x城镇的y城镇的编号
int sum=0;//用于存储最少的路径条数
int a[10000]={0};//桶，用于记录有多少个没有路径的城镇
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);//输入x and y的编号
union_(x,y);//因为x y之间有路线了，就合并它们
}
for(int i=1;i<=n;i++)//开始判断
{
int c=find_(i);//判断编号为c的城镇的“祖先”
if(!a[c])//如果这个“祖先”的编号没有被记录过的话
a[c]++,sum++;//那么就记录它，节点数加一。
}
printf("%d
",sum-1);//因为有n个不同的集合，那么就至少要n-1条边才能把它们连起来。
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int pre[1000001],n,m,ans;
inline int Find(int x){
return pre[x]==x?x:pre[x]=Find(pre[x]);
}
inline void Union(int x, int y){
int fx=Find(x),fy=Find(y);
if(fx!=fy) pre[fx]=fy;
}
int main()
{
while(scanf("%d",&n)&&n){
ans=0;
scanf("%d", &m);
for(int i=1;i<=n;i++) pre[i]=i;
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
Union(x,y);
}
for(int i=1;i<=n;i++){
if(Find(i)==i) ans++;
}
printf("%d
",ans-1);
}
return 0;
}