题解：AT_abc399_c [ABC399C] Make it Forest

exLucas · 2025-03-30 07:24:28 · 题解

显然，用并查集在输入时维护当前两个点是否连通即可，联通则答案加一，因为要把他们拆开，不联通不管。

Code

#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, res;
struct UF {
    vector<int> pa, rk;
    UF(int n) : pa(n+1), rk(n+1, 0) {
        iota(pa.begin(), pa.end(), 0);
    }
    int find(int x) {
        if(pa[x] != x)  pa[x] = find(pa[x]);
        return pa[x];
    }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(rk[x] < rk[y]) {
            pa[x] = y;
        }
        else {
            pa[y] = x;
            if (rk[x] == rk[y]) rk[x]++;
        }
        return true;
    }
};
int main() {
    scanf("%d %d", &n, &m);
    UF uf(n);
    for(int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        if(!uf.unite(u, v)) {
            res ++;
        }
    }
    cout << res;
    return 0;
}