PAT甲级 - 1021 Deepest Root （25 分）

左手的ㄟ右手 2022-03-17 01:16 303阅读 0赞

题目链接：PAT甲级 - 1021 Deepest Root （25 分）

A graph which is connected and acyclic can be considered a tree. The hight of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤104) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N−1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components where K is the number of connected components in the graph.

Sample Input 1:

  1. 5
  2. 1 2
  3. 1 3
  4. 1 4
  5. 2 5

Sample Output 1:

  1. 3
  2. 4
  3. 5

Sample Input 2:

  1. 5
  2. 1 3
  3. 1 4
  4. 2 5
  5. 3 4

Sample Output 2:

  1. Error: 2 components

发表评论

表情：
评论列表 （有 0 条评论，303人围观）

还没有评论，来说两句吧...

相关阅读