1021 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 (≤) 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:

Sample Output 1:

3
4
5

Sample Input 2:

Sample Output 2:

Error: 2 components

题意：

　　一个图可以看成是一棵树，这颗树的高度取决于所选的根节点。输出使树的高度最高的根节点。如果所给出的图不能够用树来表示，则输出图中连通分量的个数。

思路：

　　用DFS深搜找出连通分量的个数，第一次深搜找出以一号结点作为根节点的深度最大的那个结点，然后再一次结点进行第二次深搜，找出深度最深的结点。

Code：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int n;
 6 vector<int> ans;
 7 vector<bool> visited;
 8 vector<vector<int> > grap;
 9 int max_deep = 0;
10 
11 void DFS(int node, int level) {
12     if (max_deep < level) {
13         ans.clear();
14         ans.push_back(node);
15         max_deep = level;
16     } else if (max_deep == level) {
17         ans.push_back(node);
18     }
19     visited[node] = true;
20     for (int it : grap[node]) {
21         if (visited[it] == false) {
22             DFS(it, level + 1);
23         }
24     }
25 }
26 
27 int main() {
28     int v1, v2;
29     cin >> n;
30     grap.resize(n + 1);
31     visited.resize(n + 1, false);
32     for (int i = 1; i < n; ++i) {
33         cin >> v1 >> v2;
34         grap[v1].push_back(v2);
35         grap[v2].push_back(v1);
36     }
37     int count = 0, s1 = 0;
38     set<int> s;
39     for (int i = 1; i <= n; ++i) {
40         if (visited[i] == false) {
41             DFS(i, 1);
42             if (i == 1) {
43                 if (ans.size() != 0) s1 = ans[0];
44                 for (int it : ans) s.insert(it);
45             }
46             count++;
47         }
48     }
49 
50     if (count > 1) {
51         cout << "Error: " << count << " components" << endl;
52     } else {
53         ans.clear();
54         max_deep = 0;
55         visited.clear();
56         visited.resize(n + 1, false);
57         DFS(s1, 1);
58         for (int it : ans) s.insert(it);
59         for (int it : s) cout << it << endl;
60     }
61     return 0;
62 }

参考：

　　https://www.liuchuo.net/archives/2348