CFR 699 D. Fix a Tree ( Constructing )

Problem - D - Codeforces
構造題。
題目給N個點和其各自的父親，若父親為自己就是根。求改變最少的父親使成為一棵樹。
首先想到根只有一個，且如果原本就有根存在（自己的父親是自己），那麼就選它做根。
而如果天生有多數這樣的根，其他根就必須重新導向被挑選的根。直覺的是可以任意挑選根。
但若天生不存在這樣的根，那麼。。。
先考慮每當產生一個環，就必須將任意其中一個節點重新導向環以外的節點; 又直接導向決定好的根顯然最優。
。。。所以如果天生不存在根，就將其中一個環裡的節點當作根，環也順便解開了。
若圖上不存在環，又只有一個節點導向自己，那麼就一定是一棵樹。

struct UnionFind{
    vi fa;
    UnionFind( int sz ){
        fa.resize( sz );
        for( int i = 0; i < fa.size(); ++i )
            fa[ i ] = i;
    }
    int find( int x ){
        if( fa[ x ] == x ) return x;
        return fa[ x ] = find( fa[ x ] );
    }
    bool unite( int a, int b ){
        int x = find( a );
        int y = find( b );
        if( x == y ) return false;
        fa[ x ] = y; return true;
    }
};

void solve(){
    int N; cin >> N;
    UnionFind uf = UnionFind( N );

    vi A( N );
    for( int i = 0; i < N; ++i ){
        cin >> A[ i ];
        --A[ i ];
    }

    vi root, cycle_edge;
    for( int i = 0; i < N; ++i ){
        if( A[ i ] == i ) root.push_back( i );
        else{
            if( uf.find( A[ i ] ) == uf.find( i ) ) // cycle will form
                cycle_edge.push_back( i );
            else
                uf.unite( A[ i ], i );
        }
    }

    int chg_cnt = 0;
    vi ans = A;
    if( root.empty() ){
        if( not cycle_edge.empty() ){
            ++chg_cnt;
            ans[ cycle_edge.front() ] = cycle_edge.front();
            for( int i = 1; i < cycle_edge.size(); ++i )
                ++chg_cnt,
                ans[ cycle_edge[ i ] ] = cycle_edge.front();
        }
    } else{
        for( int i = 1; i < root.size(); ++i )
            ++chg_cnt,
            ans[ root[ i ] ] = root.front();
        for( int i = 0; i < cycle_edge.size(); ++i )
            ++chg_cnt,
            ans[ cycle_edge[ i ] ] = root.front();
    }

    cout << chg_cnt << "\n";
    for( int i = 0; i < ans.size(); ++i )
        cout << ans[ i ] + 1 << ( i + 1 == ans.size() ? '\n' : ' ' );
}