*[codility]Country network

浏览数：67 / 时间：2015年06月09日

https://codility.com/programmers/challenges/fluorum2014

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1273

http://blog.csdn.net/caopengcs/article/details/36872627

http://www.quora.com/How-do-I-determine-the-order-of-visiting-all-leaves-of-a-rooted-tree-so-that-in-each-step-I-visit-a-leaf-whose-path-from-root-contains-the-most-unvisited-nodes#

思路如曹博所说，先dfs记录离根的距离，来的方向的前驱。然后按距离排序，之后按此排序求有意义的增加距离。

直观感受是，如果两个叶子在一个分叉上，显然深的节点更先被访问，如果不在一个分叉上，那么先算深的也没什么损失。最后，按照这个权值再对叶子排序一次，就是所要的结果。

#include <iostream>
using namespace std;
void dfs(vector<vector<int>> &tree, vector<int> &parent, vector<int> &depth, vector<bool> &visited, int root, int dep) {
    visited[root] = true;
    depth[root] = dep;
    for (int i = 0; i < tree[root].size(); i++) {
        if (visited[tree[root][i]])
            continue;
        parent[tree[root][i]] = root;
        dfs(tree, parent, depth, visited, tree[root][i], dep + 1);
    }
}

vector<int> solution(int K, vector<int> &T) {
    int n = T.size();
    vector<vector<int>> tree(n);
    for (int i = 0; i < n; i++) {
        if (T[i] != i) {
            tree[i].push_back(T[i]);
            tree[T[i]].push_back(i);
        }
    }
    vector<int> parent(n);
    vector<int> depth(n);
    vector<bool> visited(n);
    dfs(tree, parent, depth, visited, K, 0);
    vector<vector<int>> cnt(n);
    for (int i = 0; i < n; i++) {
        cnt[depth[i]].push_back(i);    
    }
    vector<int> ordered;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < cnt[i].size(); j++) {
            ordered.push_back(cnt[i][j]);    
        }
    }
    vector<int> res;
    vector<int> length(n);
    visited.clear();
    visited.resize(n);
    visited[K] = true;
    for (int i = 0; i < ordered.size(); i++) {
        int len = 0;
        int x = ordered[i];
        while (!visited[x]) {
            visited[x] = true;
            x = parent[x];
            len++;
        }
        length[ordered[i]] = len;
        //cout << "length[" << ordered[i] << "]:" << len << endl;
    }
    
    cnt.clear();
    cnt.resize(n);
    for (int i = 0; i < length.size(); i++) {
        cnt[length[i]].push_back(i);    
    }
    res.push_back(K);
    for (int i = cnt.size() - 1; i > 0; i--) {
        for (int j = 0; j < cnt[i].size(); j++) {
            res.push_back(cnt[i][j]);
        }
    }
    return res;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

*[codility]Country network