题解 | 畅通工程

#include <iostream>
#include <cstdio>

using namespace std;

int father[1010];

void init( int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

int findroot(int u) {
    if (u == father[u]) {
        return u;

    } else {
        father[u] = findroot(father[u]);//压缩路径
        return father[u];
    }
}
int setcount;  //记录集合数
void unionset(int u, int v) {
    int uroot = findroot(u);
    int vroot = findroot(v);
    if(uroot!=vroot){
        setcount--;
    }
    father[vroot] = uroot;

}
int main() {
   int m,n ;
   while (scanf("%d%d",&n,&m)!=EOF) {
    if(n==0){
        break;
    }
    setcount=n;
    init(n+1);
    while (m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        unionset(u, v);
    
    }
    printf("%d\n",setcount-1);//n个城市需n-1条路
   
   }
    return 0;
}