PAT 1021 Deepest Root

  1. 1. Deepest Root

Deepest Root

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.

Input Specification

Each input file contains one test case. For each case, the first line contains a positive integer N (≤10​^4​​) 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
2
3
4
5
5
1 2
1 3
1 4
2 5

Sample Output 1

1
2
3
3
4
5

Sample Input 2

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

Sample Output 2

1
Error: 2 components

去年连答案都看不懂的题在今天发愣的时候突然想出来，真是可喜可贺。

题目要求是求树高，但其实树高其实和求路径长度是一致的：在简单图里，只要定了起点和终点，路径就是从根到叶节点的轨迹。求某点的最大路径长度和全图强连通分量可以用dfs一并解决，问题转化为求全图的最大路径长度

简单粗暴的穷举会被几个测试点卡时间，所以需要一些“聪明”的小办法。仔细思考，穷举被卡时间的原因应该是做了大量重复的计算。如果能区分哪些计算是不必要的，就可以解决问题。沿着这个思路，考虑两条最长路径是否有关系。考虑十字型的图，两条最长路径相交于图上一点，这么看来最长路径之间很可能有交点。就从交点出发吧。

考虑连通图的情况。若A为图上一点，B为图上另一点。两点间的最长路径，记作MaxPath(A,B)

设S为图上任意一点，从S出发的最长路径的终点为P。那么P点的出度一定为0：若出度不为0，总可以找到更长的路径。从而与S，P之间路径为最长矛盾。

设从P点出发的最长路径的终点为Q，则MaxPath(P,Q)一定经过S点：假设这条路不经过S点。设T为属于Path(P,Q)且不属于Path(P,S)的任意一点。因为图联通，则S，T间存在长度至少为1的路径。那么S，P间经过T的路径长度比Path(S,P)更长，与Path(S,P)是S和P点间最长路径的假设矛盾。所以MaxPath(P,Q)一定经过S点。而P点和Q点必定一个入度为0，一个出度为0(P，Q位于图的两端)。因此，Path(P,Q)即为整张图的最长路径。

回到本题，要求所有最长路径的起始节点，任选一个节点S，所有使路径最长的P都是路径的起始节点。需要注意的是，当Path(P，Q)在最长路径时，P点和Q点都可以作为节点。这是因为路径是可以反向的。求出所有的P，Q去重排序后即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "cstdio"
#include "vector"
#include "algorithm"
#include "set"
using namespace std;
int graph[10086][10086];
int n;
int max_depth = -1;
vector<int> roots;
set<int> ans = set<int>();
bool visited[10086];
void dfs(int source, int depth)
{
	visited[source] = true;
	if (depth > max_depth)
	{
		max_depth = depth;
		roots.clear();
	}
	if (depth == max_depth) roots.push_back(source);
	for (int i = 1; i <= n; i++)
		if (graph[source][i] == 1 && !visited[i])
			dfs(i, depth + 1);
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int j, k;
		scanf("%d %d", &j, &k);
		graph[j][k] = graph[k][j] = 1;
	}
	fill(visited, visited + 10086, false);
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!visited[i]) { dfs(i, 0); cnt++; }
	}
	if (cnt != 1) { printf("Error: %d components\n", cnt); return 0; }
	for (auto i : roots) ans.insert(i);
	fill(visited, visited + 10086, false);
	dfs(roots[0], 0);
	for (auto i : roots) ans.insert(i);
	for (auto i : ans) printf("%d\n", i);
	return 0;
}
PAT
prev： next：