题解 | #畅通工程#

#include <iostream>
using namespace std;
int n;
//x为下标
int getFather(int arr[],int x){
    while(arr[x] !=-1){
        x = arr[x];
    }
    return x;
}
void joint(int arr[],int a,int b){
    int aFather = getFather(arr,a);
    int bFather = getFather(arr,b);
    if(aFather == bFather)return;
    arr[aFather] = bFather;
}
int main() {
    int m;//n个城镇，m条路
    while(cin>>n>>m){
        int towns[n+1];//0丢弃，编号1-n
        for(int i =0;i<=n;i++)towns[i]=-1;//都为独立节点
        int a,b;
        while(m--){
            cin>>a>>b;
            joint(towns,a,b);
        }
        int count=-1;
        for(int i=1;i<=n;i++)
            if(towns[i]==-1)count++;
        cout<<count<<endl;
    }
}
// 64 位输出请用 printf("%lld")

并查集的应用