【小码匠自习室】并查集裸题：ABC288 - C - Don’t be cycle

6 7
1 2
1 3
2 3
4 2
6 5
4 6
4 5

2

4 2
1 2
3 4

0

5 3
1 2
1 3
2 3

1

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
 
struct edge {
    int from;
    int to;
};
 
struct UF {
    vector<int> fa;
 
    UF (int n) :
                fa(n) {}
 
    void initialize (int n) {
        for (int i = 0; i < n; ++i) {
            fa[i] = i;
        }
    }
 
    int find(int a) {
        if (a != fa[a]) {
            fa[a] = find(fa[a]);
        }
        return fa[a];
    }
 
    void unite(int x, int y) {
        int a = find(x);
        int b = find(y);
        if (a != b) {
            fa[b] = a;
        }
    }
 
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
};
 
void best_coder() {
    int n, m;
    cin >> n >> m;
    queue<edge> g;
    UF uf(n);
    uf.initialize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g.push({a, b});
    }
    int ans = 0;
    while (!g.empty()) {
        int a = g.front().from;
        int b = g.front().to;
        g.pop();
        if (uf.is_same(a, b)) {
            ++ans;
            continue;
        }
        uf.unite(a, b);
    }
    cout << ans;
}
 
void happy_coder() {
}
 
int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    // 小码匠
    best_coder();
 
    // 最优解
    // happy_coder();
 
    // 返回
    return 0;
}

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>
 
using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T>, greater<T>
 
template<typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
 
const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;
 
// UnionFind,素集合データ構造,DisjointSet
 
template<typename weight_type = int>
class union_find {
    static_assert(
            std::is_arithmetic<weight_type>::value,
            "Invalid weight type");
private:
    const std::function<void(int, int)> noop = [](int aa, int bb) {};
 
    std::vector<int> uni;
    std::vector<int> edge_count_;
    std::vector<weight_type> weights;
    int size_;
 
    const void check(const int n) const {
        if (this->group_size() < 0) {
            assert(false);
        }
        if (!(0 <= n && n < this->all_size())) {
            assert(false);
        }
    }
 
public:
    union_find() : uni(0), edge_count_(0), weights(0), size_(-1) {}
 
    union_find(const int n)
            : uni(n, -1), edge_count_(n), weights(n), size_(n) {
        this->check(n - 1);
    }
 
    union_find(const std::vector<weight_type> &_weights)
            : uni(_weights.size(), -1), edge_count_(_weights.size()),
              weights(_weights), size_(_weights.size()) {
        this->check((int) _weights.size() - 1);
    }
 
    bool same(const int a, const int b) {
        this->check(a);
        this->check(b);
        return this->find(a) == this->find(b);
    }
 
    int find(const int a) {
        this->check(a);
        return this->uni[a] < 0 ?
               a :
                this->uni[a] = this->find(this->uni[a]);
    }
 
    bool unite(int a, int b) {
        return unite(a, b, noop);
    }
 
    bool unite(int a, int b, const std::function<void(int, int)> &f) {
        a = this->find(a);
        b = this->find(b);
        this->edge_count_[a]++;
        if (a == b) {
            return false;
        }
        this->size_--;
        if (this->uni[a] > this->uni[b]) {
            std::swap(a, b);
        }
        f(a, b);
        this->uni[a] += this->uni[b];
        this->weights[a] += this->weights[b];
        this->edge_count_[a] += this->edge_count_[b];
        this->uni[b] = a;
        return true;
    }
 
    const int group_size() const {
        return this->size_;
    }
 
    const int all_size() const {
        return this->uni.size();
    }
 
    const int size(const int a) {
        this->check(a);
        return -this->uni[this->find(a)];
    }
 
    const int edge_count(const int a) {
        this->check(a);
        return this->edge_count_[this->find(a)];
    }
 
    const weight_type weight(const int a) {
        this->check(a);
        return this->weights[this->find(a)];
    }
};
 
 
void solve() {
    int N, M;
    cin >> N >> M;
    union_find<> uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        uf.unite(a - 1, b - 1);
    }
 
    int ok_cnt = 0;
    set<int> checked;
    for (int i = 0; i < N; ++i) {
        const auto par = uf.find(i);
        if (checked.count(par)) continue;
        checked.emplace(par);
        ok_cnt += uf.size(par) - 1;
    }
 
    cout << max(M - ok_cnt, 0) << "\n";
}
 
int main(void) {
#ifndef ONLINE_JUDGE
    const auto in_stream = freopen("../in.txt", "r", stdin);
    if (in_stream == nullptr) {
        cerr << "ERROR!" << endl;
        return 1;
    }
#endif
 
    solve();
 
#ifndef ONLINE_JUDGE
    fclose(in_stream);
#endif
}