题解：CF698B Fix a Tree

lsd110504lsd · 2025-12-16 20:20:19 · 题解

简单题

分析

手玩样例可以发现，给我们的原图可能是若干的树和环（请读者自证），当我们有树又有环（或只有树）时，可以把环上任意一点连到树根；如果只有环时，先给其中一个环上的任意一个点，使它的 fa_x = x，然后按上一种情况处理即可。维护使用并查集维护。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+5;
int idx;
int ans;
int fa[N],res[N],tot[N],a[N];
inline int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
vector<int> G[N];
int vis[N];
inline void Dfs(int u,int fa,int& ifs){
    if(vis[u]){
        ifs=1;
        return  ;
    }
    vis[u]=1;
    for(auto v:G[u]){
        if(v==fa)   continue;
        Dfs(v,u,ifs);
    }
}
map<int,int> mp;
int ifs_circ[N];
int main(){
    // freopen("C.in","r",stdin);
    // freopen("C.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)   fa[i]=i;
    for(int i=1;i<=n;i++)   {
        cin>>a[i];

        if(a[i]==i)  continue;
        G[i].push_back(a[i]);
        G[a[i]].push_back(i);
        fa[i]=find(a[i]);
    }
    for(int i=1;i<=n;i++){
        if(mp[find(i)]==0){
            tot[++idx]=find(i);
            mp[find(i)]=1;
        }
    }
    int cnt=0,p=1;
    for(int i=1;i<=idx;i++){
        Dfs(tot[i],0,ifs_circ[i]);
        if(ifs_circ[i]==1){
            cnt++;
        }
        if(ifs_circ[i]==0) p=i;
    }
    if(cnt==idx){
        a[find(tot[1])]=find(tot[1]);
        for(int i=2;i<=idx;i++){
            a[find(tot[i])]=find(tot[1]);
            ans++;
        }
        ans++;
    }
    else 
      for(int i=1;i<=idx;i++){
          if(p!=i){
              a[find(tot[i])]=find(tot[p]);
              ans++;
          }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)   cout<<a[i]<<" ";
    return 0;
}