题解：AT_abc392_e [ABC392E] Cables and Servers

smart_kai · 2025-02-15 19:50:59 · 题解

想要连接几个块，想到使用并查集。用并查集维护块的连接情况，枚举每条边，如果一条边连接的两端已经在同一个连通块内，那么这条边就应该用来连接其他块。枚举这些边，选择另外一个块，将他们连接即可。

#include <bits/stdc++.h>
#define ll long long
#define fro for
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define pi pair<int, int>
#define ui unordered_map<int, int>
using namespace std;

// 用的是jiangly的模板
struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

int n, m;
pair<int, int> g[200010];
vector<int> rem;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    DSU dsu;
    dsu.init(n);
    for (int i=1; i<=m; i++)
    {
        cin >> g[i].first >> g[i].second;
        if (!dsu.merge(g[i].first-1, g[i].second-1))
            rem.push_back(i);
    }
    set<int> st;
    for (int i=0; i<n; i++)
    {
        if (st.find(dsu.find(i))==st.end()) st.insert(dsu.find(i));
    }
    int minOperations = st.size() - 1;
    cout << minOperations << "\n";
    for (int _=0; _ < minOperations; _++)
    {
        int cur = rem.back(), mergeto = *st.rbegin();
        cout << cur << " ";
        if (dsu.find(g[cur].first-1) == dsu.find(mergeto) && dsu.find(g[cur].second-1) == dsu.find(mergeto))
            mergeto = *st.begin();
        if (dsu.find(g[cur].first-1) == dsu.find(mergeto))
        {
            cout << g[cur].second << " " << mergeto+1 << "\n";
            dsu.merge(dsu.find(g[cur].second-1), dsu.find(mergeto));
        }
        else 
        {
            cout << g[cur].first << " " << mergeto+1 << "\n";
            dsu.merge(dsu.find(g[cur].first-1), dsu.find(mergeto));
        }
        st.erase(mergeto); rem.pop_back();
    }
    return 0;
}