Reforma DSU.cpp

#include <cstdio>
#include <algorithm>
#include <vector>

constexpr int maxn = 1e5+10;

struct DSU {
    int pai[maxn], peso[maxn];
    DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
    int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if(a == b) return 1;
        if(peso[a] < peso[b]) std::swap(a, b);
        pai[b] = a;
        peso[a] += peso[b];
        return 0;
    }
} dsu;

std::vector<std::pair<int,int>> ans;

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for(int i = 0, a, b; i < m; i++) {
        scanf("%d %d", &a, &b);
        if(dsu.join(a, b))
            ans.push_back({a, b});
    }
    printf("%ld\n", ans.size());
    for(std::pair<int,int> p : ans)
        printf("%d %d\n", p.first, p.second);
}