题解 | 村村通工程

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int f[N];
int find(int x){
    if(f[x]!=x)f[x]=find(f[x]);
    return f[x];
}

struct node{
    int x,y;
}a[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=0;i<m;i++){
        cin>>a[i].x>>a[i].y;
    }

    int cnt=0;
    for(int i=0;i<m;i++){
        int u=find(a[i].x);
        int v=find(a[i].y);
        if(u!=v){
            f[u]=v;
        }
    }
    for(int i=1;i<=n;i++){
        if(f[i]==i)cnt++;
    }
    cout<<cnt-1;
}

经典的并查集的考察，首先看见城镇以及路，就想到了图，再看问题，求还需要修建几条路使得联通，翻译为至少几条边使得各个节点连接，那么可以使用并查集，不联通就使得节点共同指向一个父节点。最后查看哪些节点也就是城镇自己指向自己，也就是与其它城镇没相连（除了共同的那个根节点），每次ans++,最后减去根节点即可