原文请訪问：

畅通project

Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

 

Description

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

 

Input

測试输入包括若干測试用例。每一个測试用例的第1行给出两个正整数。各自是城镇数目N ( < 1000 )和道路数目M。随后的M行相应M条道路。每行给出一对正整数。各自是该条道路直接连通的两个城镇的编号。

为简单起见。城镇从1到N编号。 

注意:两个城市之间能够有多条道路相通,也就是说

3 3

1 2

1 2

2 1

这样的输入也是合法的

当N为0时，输入结束，该用例不被处理。 

 

Output

对每一个測试用例，在1行里输出最少还须要建设的道路数目。 

 

Sample Input

4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0

#include
          
           #include
           
            using namespace std;const int max1=1010; int f[max1]; int find(int a) {	 if(f[a]==-1) return a;	 else return f[a]=find(f[a]); } void bing(int a,int b) {	 int t1,t2;	 t1=find(a);	 t2=find(b);	 if(t1!=t2)		 f[t1]=t2; }int main(){	int i,j,k,m,n;	while(cin>>n&&n)	{		cin>>m;		memset(f,-1,sizeof(f));     for(i=1;i<=m;i++)	 {		 cin>>j>>k;		 bing(j,k);	 }	 int ans=0;	 for(i=1;i<=n;i++)	 {		// cout<
            
             <<' ';		 if(f[i]==-1)			 ans++;	 }		 cout<
             
              <
             
            
           
          

 

版权声明：本文博主原创文章。博客，未经同意不得转载。