1. 首页
2. 并查集
3. 本页

Codeforces 698B Fix a Tree (并查集)

传送门：点我查看~~

题意：~~

思路：只需要判断根是否有冲突，还有是否会形成环的情况~处理环的情况，利用并查集判断是否有环，再将其设为根，最后再解决根的冲突~~

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< PI, int> PII;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int mx=1100;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1

int a[200000+10];
int fa[200000+10];

int fd(int x)
{
    if(x!=fa[x])
    return fa[x]=fd(fa[x]);
    return x;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        fa[i]=i;
    }
    int cnt=0;
    int root=-1;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if(a[i]==i)
        {
            root=i;
            cnt++;
        }
        else
        {
            int x=fd(i);
            int y=fd(a[i]);
            if(x==y)
            {
                a[i]=i;
                cnt++;
            }
            else
            {
                fa[x]=y;
            }
        }
    }
    if(root==-1)
    {
        for(int i=1;i<=n;++i)
        {
            if(a[i]==i)
                root=i;
        }
        cnt++;
    }

    cout<<(cnt-1)<<endl;
    for(int i=1;i<=n;++i)
    {
        if(a[i]==i)
            a[i]=root;
        printf(i==n?"%d\n":"%d ",a[i]);
    }

    return 0;
}