A graph which is connected and acyclic can be considered a tree. The height 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.
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.
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.
# 数据结构初始化与信息读入 num_nodes = int(input()) roads = [ for _ in range(num_nodes + 1)] for _ in range(num_nodes - 1): info = list(map(int, input().split())) roads[info].append(info) roads[info].append(info) visited = [Falsefor i in range(num_nodes + 1)] maxheight = 0 max_nodes = 
# 深度优先遍历 defdfs(node, height): global maxheight if height > maxheight: max_nodes.clear() max_nodes.append(node) maxheight = height elif height == maxheight: max_nodes.append(node) visited[node] = True for i in roads[node]: ifnot visited[i]: dfs(i, height + 1) # 计算连通分量,第一轮DFS count = 0 for i in range(1, num_nodes + 1): ifnot visited[i]: dfs(i, 1) count += 1
# 输出与进行第二次DFS if count >= 2: print("Error: %d components" % count) else: ans = set(max_nodes) maxheight = 0 visited = [Falsefor _ in range(num_nodes + 1)] dfs(max_nodes, 1) ans = ans | set(max_nodes) ans = sorted(ans) for i in ans: print(i)