首页 > 代码库 > PAT 1021 Deepest Root

PAT 1021 Deepest Root

#include <cstdio>#include <cstdlib>#include <vector>using namespace std;class Node {public:    vector<int> adj;    bool visited;    Node() : visited(false) {}};void reset_nodes(vector<Node>& nodes) {    int len = nodes.size();    for (int i=0; i<len; i++) {        nodes[i].visited = false;    }}void dfs(int idx, vector<Node>& nodes, int level, int& deepest) {    if (nodes[idx].visited) return;    Node& node = nodes[idx];    node.visited = true;    if (level > deepest) deepest = level;        int len = node.adj.size();    for (int i=0; i<len; i++) {        dfs(node.adj[i], nodes, level + 1, deepest);    }}int find_deepest_from(int idx, vector<Node>& nodes) {    int deepest = 0;    // reset visited flag of all the nodes    reset_nodes(nodes);        // find the max level from this node(as root)    dfs(idx, nodes, 0, deepest);        int parts = 1;    // check if other parts exist    for (int i = nodes.size() - 1; i>=1; i--) {        if (!nodes[i].visited) {            int dummy = 0;            dfs(i, nodes, 0, dummy);            parts++;        }    }        return parts > 1 ? -parts : deepest;}int main() {    int N = 0;    scanf("%d", &N);    vector<Node> nodes(N + 1);        for (int i=1; i<N; i++) {        int a, b;        scanf("%d%d", &a, &b);        nodes[a].adj.push_back(b);        nodes[b].adj.push_back(a);    }        int res = 0;    vector<int> deepnodes;    int deepest = 0;    for (int i=1; i<=N; i++) {        res = find_deepest_from(i, nodes);        // not connected graph, stop search        if (res < 0) {            break;        }        if (res > deepest) {            deepest = res;            deepnodes.clear();            deepnodes.push_back(i);        } else if (res == deepest) {            deepnodes.push_back(i);        }    }    if (res < 0) {        printf("Error: %d components\n", -res);    } else {        int len = deepnodes.size();        for (int i=0; i<len; i++) {            printf("%d\n", deepnodes[i]);        }    }    return 0;}

最深root的最远leaf也应该是最深root,利用这个做下优化的话速度应该会快不少。

PAT 1021 Deepest Root