Codeforces Round #363 (Div. 2) D. Fix a Tree(greedy+dsu)

题目链接
大意：给你一个序列，让你改动最少的元素使得可以构成一个有根树。
$a_1,a_2.....a_n$a1​,a2​.....an​表示 $i$i节点的父亲节点，有且只有一个节点 $i=a_i$i=ai​.
输出改动次数和改动后的序列。
思路：如果开始构不成树的话，必然存在环，同时也可能是有多个联通块，我们要做的就是把环去掉，把所有的联通块连在一起。
我们由于要保证改动次数最少的话，我们显然应该优先考虑 $x=a_x$x=ax​的点使他成为根（贪心思想）。每次dfs搜出一个联通块，然后并查集来判断是否构成环，如果构成环则必须要改变，先塞入 $tmp$tmp。如果这个联通块合法的话（即构成一个合法子树），我们可以随便选一个其中的点当根。
注意当联通快只有一个元素的时候要记录一下塞入 $one$one集合。
然后如果还没选根的话贪心从备选集合选一个即可（先从one中选,再从tmp中选）。
细节见代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,a[N],cnt;
vector<int>v[N],link[N],edg[N];
int vis[N];
void dfs(int o,int now){
    vis[o]=1;
    link[now].pb(o);
    for(auto k:v[o]){
        if(!vis[k])dfs(k,now);
    }
}
int f[N];
int find(int x){return f[x]==x?f[x]:(f[x]=find(f[x]));}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],f[i]=i;
    for(int i=1;i<=n;i++){
        v[i].pb(a[i]);
        v[a[i]].pb(i);
    }
    int root=0;
    vector<int>tmp,one;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i,++cnt);
            int sta=0;
            if(link[cnt].size()==1){one.pb(i);continue;}
            for(int k:link[cnt]){
                int x=find(k);
                int y=find(a[k]);
                if(x!=y)f[x]=y;
                else{//成环了，必须要改变一个
                    sta=1;
                    if(a[k]==k)tmp.pb(k),root=k;
                    else tmp.pb(a[k]);
                }
            }
            if(!sta)root=i;
        }
    }
    if(!root&&one.size())root=one.back();
    else if(!root)root=tmp.back();
    if(root!=a[root])ans++;
    a[root]=root;
    for(auto k:tmp){
        if(a[k]==root)continue;
        a[k]=root,ans++;
    }
    for(auto k:one){
        if(a[k]==root)continue;
        a[k]=root,ans++;
    }
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
    return 0;
}