Codeforces Round #363 (Div. 2) D. Fix a Tree __ dfs+剪枝+标记数组

Source

Codeforces Round #363 (Div. 2)

My Solution

dfs+剪枝+标记数组

找到第一个环把其中的一个点作为 root，然后每个环切去一条边。

找root的时候优先找自环的环，如果有自环的环，则 剩余的环每个环去掉一条边把环连到root上 环的个数 - 1 个操作；

如果没有自环的环，则有 环的个数 个操作。

具体操作 用dfs+标记数组实现，且需要剪枝不然可能有大量重复或者部分重复的dfs

用 bool flag[maxn]表示本次dfs访问过的点，当出现 flag[fatehr[v]] == true 时有环，且flag数组要在dfs回溯的时候重置好，方便下一个dfs使用。

用 bool vis[maxn] 数组标记，每个点在本次运行只访问一次，如果被先前访问过了就continue；

在dfs的时候，如果 flag[father[v]] == false && vis[father[v]] == true，则该点在以前的dfs中(非本次dfs)被访问过，就不用再次访问了。
//因为接下来的部分在先前的dfs中已经处理掉了

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;

int father[maxn], root, ans;
bool flag[maxn], vis[maxn];
void _find(int v)
{   if(flag[father[v]]){
        if(root == -1) root = v;
        father[v] = root;
        ans++;
        return;
    }
    if(father[v] == v){
       return;
    }
    flag[v] = true;
    vis[v] = true;
    if(!flag[father[v]] && vis[father[v]]){flag[v] = false; return;}
    //如果该点在以前的dfs中(非本次dfs)被访问过，就不用再次访问了。
    //因为接下来的部分在先前的dfs中已经处理掉了
    _find(father[v]);
    flag[v] = false;
}


int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    int n;
    ans = 0, root = -1;
    cin >> n;
    for(int i = 1; i <= n; i++){ cin >> father[i];
    }
    for(int i = 1; i <= n; i++){
        if(i == father[i]) {if(root == -1) root = i;else ans++;  father[i] = root;}
    }
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;         //如果该点被访问过，就不用再次访问了
        if(i != root){
            _find(i);
        }
    }
    cout << ans << "n";
    cout << father[1];
    for(int i = 2; i <= n; i++) cout << " " << father[i];


    #ifdef LOCAL
    memset(vis, false, sizeof vis);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx