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

题目链接
大意:给你一个序列,让你改动最少的元素使得可以构成一个有根树。
a 1 , a 2 . . . . . a n a_1,a_2.....a_n a1,a2.....an表示 i i i节点的父亲节点,有且只有一个节点 i = a i i=a_i i=ai.
输出改动次数和改动后的序列。
思路:如果开始构不成树的话,必然存在环,同时也可能是有多个联通块,我们要做的就是把环去掉,把所有的联通块连在一起。
我们由于要保证改动次数最少的话,我们显然应该优先考虑 x = a x x=a_x x=ax的点使他成为根(贪心思想)。每次dfs搜出一个联通块,然后并查集来判断是否构成环,如果构成环则必须要改变,先塞入 t m p tmp tmp。如果这个联通块合法的话(即构成一个合法子树),我们可以随便选一个其中的点当根。
注意当联通快只有一个元素的时候要记录一下塞入 o n e 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;
}
全部评论

相关推荐

感性的干饭人在线蹲牛友:🐮 应该是在嘉定这边叭,禾赛大楼挺好看的
点赞 评论 收藏
分享
听说改名字就能收到offer哈:Radis写错了兄弟
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务