题解 | 畅通工程

#include <iostream>
#include <vector>
using namespace std;

vector<int> father(1010);
int setCount;
void Init(int n){
    for(int i=0;i<n;i++){
        father[i] = i;
    }
}

int findRoot(int cur){
    if(cur==father[cur]){
        return cur;
    }else{
        father[cur] = findRoot(father[cur]);
        return father[cur];
    }
}

void unionSet(int c1,int c2){
    int root1 = findRoot(c1);
    int root2 = findRoot(c2);
    if(root1!=root2){
        setCount--;
    }
    father[root1] = root2;
}

int main() {
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0) break;
        Init(n+1);
        setCount = n;
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            unionSet(a,b);
        }
        printf("%d\n",setCount-1);
    }
}


// 64 位输出请用 printf("%lld")