Fix a Tree【Codeforces 699 D】【dfs + 树的性质】

Codeforces Round #363 (Div. 2) D

  题意：有N个点，每个点i都有一个父节点p[i]，如果“i == p[i]”则是说明i结点是根结点，现在我们给出这样的1～N的p[i]，这可能是不合法的，问，我们应该最少改变多少个使它变成一棵合法的树。

  思路：有两种情况，一种是多棵树，另一种是一个环，也就是这个块是没有树，他们构成了一个环，如果是一个环的话，拆解环上任意一个结点都是可以的，去让它成为根结点，或者去连接上已经有的根结点，如果现在变成了个森林的图，我们要把多出来的根结点连接到其他的树的结点上面去。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, head[maxN], cnt, p[maxN], root[maxN], num = 0, ans = 0, Stap[maxN], Stop = 0, rt;
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN];
inline void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
bool vis[maxN] = {false}, flag, used[maxN];
int id = 0, ST[maxN], ss;
inline void dfs(int u)
{
    vis[u] = true;
    ST[++ss] = u;
    used[u] = true;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(!flag && used[v])
        {
            flag = true;
            id = v;
            continue;
        }
        else if(used[v] || vis[v]) continue;
        dfs(v);
    }
}
inline void init()
{
    cnt = 0;
    for(int i=1; i<=N; i++) head[i] = -1;
}
int main()
{
    scanf("%d", &N);
    init();
    for(int i=1; i<=N; i++)
    {
        scanf("%d", &p[i]);
        if(p[i] == i) { root[++num] = i; continue; }
        addEddge(p[i], i);
    }
    for(int i=1; i<=N; i++) Stap[++Stop] = i;
    rt = 0;
    while(num)
    {
        id = root[num];
        rt = root[num];
        dfs(root[num]);
        num--;
        if(num)
        {
            ans++;
            p[id] = root[num];
        }
    }
    while(Stop)
    {
        while(Stop && vis[Stap[Stop]]) Stop--;
        if(!Stop) break;
        id = 0;
        flag = false;
        dfs(Stap[Stop]);
        while(ss) used[ST[ss--]] = false;
        if(!flag) continue;
        ans++;
        if(!rt) { p[id] = id; rt = id; }
        else p[id] = rt;
    }
    printf("%d\n", ans);
    for(int i=1; i<=N; i++) printf("%d ", p[i]);
    puts("");
    return 0;
}