CF22E 题解

题面

注意到题目给的图为基环树森林。

因为一个（\(n>1\)）的强连通图每个点都要有出度和入度，所以：

对于每个基环树，叶子结点是没有入度的，所以一定要有一条从环上出发的路径经过这个点。

对于基环树的环，注意到它缩点后没有出度，所以一定要有一条出边。

注意到叶子结点的需求和根节点相反，所以可以从根节点边到叶子结点，这样可以最大化配对的数量。

构造方法为：考虑从（缩点后的）树 \(T1\) 的根节点连向 \(T2\) 的叶子结点（如果没有叶子就连根），再从 \(T2\) 的根节点开始继续连边。

特别地：\(Tn\) 向 \(T1\) 连边。如果只有一棵树就是 \(T1\) 的根向自己叶子连边。

对于还没有入度的叶子，随便找个有入度的叶子，向这些没入度的叶子连边就可以了。

因为最大化了配对的数量，答案为有需求的点减去配对数量，所以答案一定最小。

缩点和找每一棵树的叶子可以用并查集解决，写起来更简单。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
int deg[N], n, fa[N];

vector<int> lf[N];

int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) fa[i] = i;
    for(int i = 1; i <= n; i ++)
    {
        int x; cin >> x;
        fa[find(i)] = find(x);
        deg[x] ++;
    }
    vector<int> rt;
    for(int i = 1; i <= n; i ++)
    {
        if(!deg[i]) lf[find(i)].push_back(i);
        if(find(i) == i) rt.push_back(i);
    }
    vector<pair<int, int>> ans;
    int lst;
    for(int i = 0; i < rt.size(); i ++)
    {
        int u = rt[i], v = rt[(i + 1) % rt.size()];
        int x = rt[i], y;
        if(lf[v].empty()) y = v;
        else y = lf[v].back(), lf[v].pop_back();
        if(x != y) ans.push_back({x, y});
        lst = y;
    }
    for(int i : rt)
    for(int j : lf[i])
        ans.push_back({lst, j});
    cout << ans.size() << "\n";
    for(auto [x, y] : ans) cout << x << " " << y << "\n";

    return 0;
}