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 componentswhere K is the number of connected components in the graph.
Sample Input 1:
51 21 31 42 5
Sample Output 1:
345
Sample Input 2:
51 31 42 53 4
Sample Output 2:
Error: 2 components
1 #include2 #include 3 #include 4 using namespace std; 5 vector >G; 6 int N, maxH = 0; 7 bool visit[10010]; 8 set res; 9 vector temp;10 11 void DFS(int node, int H)12 {13 if (H > maxH)14 {15 temp.clear();16 temp.push_back(node);//更新新的根节点17 maxH = H;18 }19 else if (H == maxH)20 temp.push_back(node);//相同的最优解21 visit[node] = true;22 for (int i = 0; i < G[node].size(); ++i)23 if (visit[G[node][i]] == false)24 DFS(G[node][i], H + 1);25 }26 27 int main()28 {29 int a, b, s1 = 0, cnt = 0;30 cin >> N;31 G.resize(N+1);32 for (int i = 1; i < N; ++i)33 {34 cin >> a >> b;35 G[a].push_back(b);36 G[b].push_back(a);37 }38 for (int i = 1; i <= N; ++i)39 {40 if (visit[i] == false)//开始深度搜索遍历，如果是一个联通区域，则只会执行一次41 {42 DFS(i, 1);43 if (i == 1)44 {45 if (temp.size() != 0)46 s1 = temp[0];47 for (int j = 0; j < temp.size(); ++j)48 res.insert(temp[j]);49 }50 cnt++;//计算集合数51 } 52 }53 if (cnt != 1)54 printf("Error: %d components\n", cnt);55 else56 {57 temp.clear();58 maxH = 0;59 fill(visit, visit + N + 1, false);60 DFS(s1, 1);61 for (int j = 0; j < temp.size(); ++j)62 res.insert(temp[j]);63 for (auto r : res)64 cout << r << endl;65 }66 return 0;67 }