畅通工程-题解(C++代码)并查集

#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"
#include "set"
using namespace std;
typedef long long ll;
const int maxn = 100010;
const int INF = 1e9;
//priority_queue<int, vector<int>, greater<int> > q;
int fa[maxn];    //并查集数组
int n, m;
//初始化并查集数组
void init() {
    for(int i = 1; i <= n; ++i) fa[i] = i;
}
//找爹函数
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
    while(true) {
        cin >> n;
        if(!n) break;
        cin >> m;
        init();
        for(int i = 0; i < m; ++i) {
            int x, y;
            cin >> x >> y;
            int p1 = find(x);
            int p2 = find(y);
            if(p1 != p2) fa[p2] = p1;
        }
        int res = 0;
        for(int i = 1; i <= n; ++i) if(fa[i] == i) res++;
        cout << res - 1 << endl;
    }
    return 0;
}