题目

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$ ( $\le 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即可。 题目还要求所给的图不是树的话，也就是说这个图不是连通的， 这时候需要知道到底有几个部分，可以对剩下DFS未遍历到的结点继续DFS知道全部遍历， 过程中记数即可。

代码

Github最新代码，欢迎交流

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <stdio.h>

typedef struct node{
	int visited, level, depth;
	struct adj *adj;
} node;

typedef struct adj{
	struct node *node;
	struct adj *next;
} adj;

void DFS(node *n, int level)
{
	n->visited = 1;
	n->level = level + 1;

	for (adj *a = n->adj; a; a = a->next)
		if (a->node->visited == 0)
			DFS(a->node, level + 1);
}

int main()
{
	int N, n1, n2, count, depth, maxdepth = 0;
	node nodes[10000] = {0}, *pnode;
	adj edges[20000] = {0}, *padj;

	/* Read and build the adjacent linked list */
	scanf("%d", &N);
	for (int i = 0; i < N - 1; i++) {
		scanf("%d %d", &n1, &n2);
		/* n1 to n2 */
		pnode = &nodes[n1 - 1];
		padj = &edges[i * 2];
		padj->node = &nodes[n2 - 1];
		padj->next = pnode->adj;
		pnode->adj = padj;
		/* n2 to n1 */
		pnode = &nodes[n2 - 1];
		padj = &edges[i * 2 + 1];
		padj->node = &nodes[n1 - 1];
		padj->next = pnode->adj;
		pnode->adj = padj;
	}

	for (int i = 0; i < N; i++) {
		/* Reset the whole graph */
		depth = 0;
		count = 1;
		for (int i = 0; i < N; i++)
			nodes[i].visited = nodes[i].level = 0;

		/* Start from the ith node */
		DFS(nodes + i, 0);

		/* Get the depth of the tree */
		for (int i = 0; i < N; i++)
			if (nodes[i].visited == 1)
				if (nodes[i].level > depth)
						depth = nodes[i].level;

		/* Try to find other disjoint components */
		for (int i = 0; i < N; i++)
			if (nodes[i].visited == 0) {
				DFS(nodes + i, 0);
				count ++;
			}

		if (count != 1) { /* If not all the nodes are visited */
			printf("Error: %d components", count);
			return 0;  /* Only have to do it once */
		} else { /* It is one tree */
			nodes[i].depth = depth;
			if (maxdepth < depth)
				maxdepth = depth;
		}
	}

	/* Find the root with the same maximum depth */
	for (int i = 0; i < N; i++)
		if (nodes[i].depth == maxdepth)
			printf("%d\n", i + 1);

	return 0;
}