题解：AT_abc392_e [ABC392E] Cables and Servers

· · 题解

考虑将服务器作为顶点、电缆作为边构成的图。

对于每个连通分量，找到属于它的顶点以及多余的边。

这通过 DFS 或 BFS 实现，也可以用并查集来完成。

修改多余边的一端总是会减少连通分量的数量。反之，无论边如何修改，连通分量的数量最多只会改变一个。

因此，重复这种修改可以最小化所需的操作次数。

可以通过优先考虑具有更多多余边的连通分量来实现点。

#include <bits/stdc++.h>
#include <atcoder/dsu>
#define int long long
using namespace std;
inline int read()
{
    int f = 0, ans = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= c == '-', c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
constexpr int N = 2e5 + 5;
int n, m;
pair<int, int> e[N];
signed main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    n = read(), m = read();
    atcoder::dsu d(n + 1);
    vector<int> id;
    for (int i = 1; i <= m; ++i)
    {
        int u = read(), v = read();
        e[i] = {u, v};
        if (d.same(u, v))
            id.emplace_back(i);
        else
            d.merge(u, v);
    }
    set<int> ldr;
    vector<tuple<int, int, int>> ans;
    for (int i = 1; i <= n; ++i)
        if (d.leader(i) == i)
            ldr.insert(i);
    for (int &i : id)
    {
        if (size(ldr) == 1)
            break;
        ldr.erase(d.leader(e[i].first));
        ans.push_back({i, e[i].second, *begin(ldr)});
        d.merge(d.leader(e[i].first), *begin(ldr));
        ldr.erase(begin(ldr));
        ldr.insert(d.leader(e[i].first));
    }
    write(size(ans)), putchar('\n');
    for (auto &[x, y, z] : ans)
        write(x), putchar(' '), write(y), putchar(' '), write(z), putchar('\n');
    return 0;
}