题解 | 畅通工程

思路：考察并查集的基本操作，根据题目要求构建并查集，初始化并查集个数为城镇个数，依次输入道路合并，最后需要建设的道路数目为并查集个数-1：

合并到最后只有1个并查集，则说明集合内结点相互连通，不用建路；

合并到最后只有2个并查集，之间要建1条路才连通；

合并到最后只有3个并查集，之间要建2条路才连通；

#include <cstring>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int father[1010];
int setCnt;//记录并查集个数
//初始化
void Initfun(int n) {
    for (int i = 1; i < n; i++) {
        father[i] = i;
    }
    return;
}
//找根结点
int FindFather(int i) {
    if (i == father[i]) {//根节点
        return i;
    } else {
        father[i]=FindFather(father[i]);
        return father[i];
    }
}
//合并并查集
void UniteSet(int a, int b) {
    if (FindFather(a) == FindFather(b)) {
        return;
    } else {
        father[FindFather(a) ] = FindFather(b);//注意不是a，b直接相连，是两者的根相连
        setCnt--;
    }
    return;
}

int main() {
    int N, M; //N城镇数，M道路数
    int a, b;
    while (scanf("%d%d", &N, &M) != EOF) {
        memset(father, 0, 1010);
        if (N == 0)break;
        //城镇为结点，道路为边，构造并查集
        Initfun(N + 1);
        setCnt = N;
        for (int i = 0; i < M; i++) {
            scanf("%d%d", &a, &b);
            UniteSet(a, b);
        }
        //合并完剩下setCnt个集合
        printf("%d\n", setCnt - 1);
    }
    return 0;
}