05 复试 畅通工程
给出m个城镇，n条路，问还需修几条路才能连通所有城镇。

基本并查集问题

#include<iostream>using namespace std;#include<memory.h>int city[1001];int find(int pos){if(city[pos]==-1)return pos;return city[pos]=find(city[pos]);}int merge(int a,int b){int roota=find(a);int rootb=find(b);if(roota==rootb)return 0;city[roota]=rootb;return 1;}int main(){int n,m;int s,e;int count;while(1){cin>>n;memset(city,-1,sizeof(city));if(n==0)break;cin>>m;while(m--){cin>>s;cin>>e;merge(s,e);}count = 0;for(int i=1;i<=n;i++){if(city[i]==-1)count++;}cout<<count-1<<endl;}}