题解：CF698B Fix a Tree

Justskr · 2025-12-16 19:25:07 · 题解

题解：并查集

一句话题意

给定一个长度为 n 的数组 a（a_i 表示节点 i 的父节点），要求通过最少次数的修改，使得数组满足：

1. 恰好有一个根节点（即唯一的 r 满足 a_r=r）；
2. 所有节点构成一棵合法的树。

最终需要输出修改次数和修改后的数组。

思路详解

首先发现，需要满足一颗合法的有根树，我们要保证无环和有根两个条件。

对于无环非常简单，我们使用并查集来判断连通块，如果发现了环的话，就将环拆掉，找一个节点重新将边连到根节点就行。

对于有根，我们需要确保唯一。

• 对于一开始有多个根的情况，我们任选一个作为根，将其他的非法根重新连一条边到我们选择的那个根。
• 对于一开始无根的情况，我们任选一个刚才在无环判断时需要进行更改的点作为根，这样显然最优。这种情况肯定可以保证至少有一个点是需要修改的，也就是肯定出现了环，否则不可能出现无根情况。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define const constexpr
#define dbug(x) (void)(cerr << #x << " = " << x << endl)
const int N = 2e5 + 86;
ll a[N], fa[N];
bool change[N];

inline ll find(ll x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
inline void merge(ll x, ll y) {
    fa[find(x)] = find(y);
}

int main() {
    ll n, root = 0, cnt = 0;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        fa[i] = i;
        if (a[i] == i) root = i;
    }
    for (ll i = 1; i <= n; i++) {
        if (i == root) continue;
        if (find(i) == find(a[i])) change[i] = 1, cnt ++;
        merge(i, a[i]);
    }
    cout << cnt << endl;
    for (ll i = 1; i <= n; i++) {
        if (change[i] == 1) {
            if (!root) root = i;
            a[i] = root;
        }
        cout << a[i] << " ";
    }

    return ~~ (0 ^ 0);
}