连通图（sf14c）

解题思路:每个连通图图间加一条路则变得连通

                    所有所要加的路线数=连通分量-1；

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N=1005;

int father[N];

//找根节点

int Find(int x)

{

if(x==father[x]) return x;

else return father[x]=Find(father[x]);//压缩路径 

} 

//合并

void Union(int a,int b)

{

int FA=Find(a);

int FB=Find(b);

if(FA!=FB)

father[FA]=FB;

} 

int main()

{

int n,m;

while(cin>>n>>m)

{

if(n==0) break;

//初始化 

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

father[i]=i;

//处理m条边

int x,y;

while(m--)

{

cin>>x>>y;

Union(x,y);

} 

//统计连通分量

int cnt=0;

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

{

if(father[i]==i) cnt++;

} 

cout<<cnt-1<<endl; 

}

}