ReZero's Utopia.

有序树转二叉树求深度

字数统计: 271阅读时长: 1 min
2016/11/02 Share

只是求个深度所以按照父子关系编码就好了

#include <bits/stdc++.h>

using namespace std;

int n, answer, prev[30010];
vector<int> G[30010];

void bfs1(int root, int step){
    //cout << "root" << root << " step : " << step <<endl;
    if(G[root].empty()){
        answer = max(answer, step);
        return;
    }
    int temp = ++step;
    for(int i = 0; i < G[root].size(); ++i){
            bfs1(G[root][i], temp);
    }
}

void bfs2(int root, int step){
    //cout << "root" << root << " step : " << step <<endl;
    for(int i = 0; i < G[root].size(); ++i){
        int temp = ++step;
        bfs2(G[root][i], temp);
    }
    answer = max(answer, step);
}

int finds(int x){
    int r = x;
    while(r != prev[r]){
        r = prev[r];
    }
    return r;
}


int main(){
    while(cin >> n){

        for(int i = 1; i <= n; ++i){
            prev[i] = i;
        }
        for(int cas = 1; cas < n; ++cas){
            int a, b;
            cin >> a >> b;
            G[a].push_back(b);
            prev[b] = a;
        }

        int root = finds(1);
        answer = 0;
        bfs1(root, 1);
        cout << answer << " ";

        answer = 0;
        bfs2(root, 1);
        cout << answer << endl;
        for(int i = 1; i <= n; ++i)
        G[i].clear();
    }
    return 0;
}

求祖宗麻烦了点,其实做个更新就好
垃圾代码,水的一逼,能过就行不多求

CATALOG