畅通工程 试读

思路

并查集求出有多少个连通分支即可，这几道并查集的题目都可以用模板解的，下面这个模板没有很完整，所以用的时候够用就行，并且其实不新建一个类也行，我只是想告诉大家整个并查集的逻辑。

#include<iostream>
#include<vector>
#include<numeric>

using namespace std;

class UF{
public:
    vector<int> fa;
    int comp_cnt;
public:
    UF(int n) : fa(n), comp_cnt(n){
        iota(fa.begin(), fa.end(), 0);
    }
    int findFa(int x){
        return x == fa[x] ? x : fa[x] = findFa(fa[x]);
    }
    void unite(int x, int y){
        x = findFa(x), y = findFa(y);
        if(x != y) {
            fa[y] = x; comp_cnt --;
        }
    }
};
int main(){
    int N, M;
    while(cin >> N >> M){
        UF uf(N);
        int x, y;
        for(int i = 0; i < M; i ++){
            cin >> x >> y;
            uf.unite(x - 1, y - 1);
        }
        cout << uf.comp_cnt - 1 << endl;
    }
    return 0;
}