首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。