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 (<=10000) 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: 5 1 2 1 3 1 4 2 5 Sample Output 1: 3 4 5 Sample Input 2: 5 1 3 1 4 2 5 3 4 Sample Output 2: Error: 2 components #include<cstdio> #include<vector> #include<set> #include<algorithm> using namespace std; const int maxn = 10000; vector<int> G[maxn]; bool vis[maxn] = {false}; int maxdepth = 0; int N; set<int> deepestroots; void DFS(int u, int depth) { if (maxdepth < depth) { maxdepth = depth; deepestroots.clear(); deepestroots.insert(u + 1); } else if (maxdepth == depth) { deepestroots.insert(u + 1); } vis[u] = true; for (int i = 0; i < G[u].size(); i++) { int t = G[u][i]; if (!vis[t]) { DFS(t, depth + 1); } } } void DFSTrave(vector<int>*G) { int count = 0; for (int i = 0; i < N; i++) { if (!vis[i]) { DFS(i, 1); count++; } } if (count == 1) { set<int>::iterator it = deepestroots.begin(); int s = *(it)-1; maxdepth = 0; fill(vis, vis + maxn, false); set<int> deepestrootstemp = deepestroots; deepestroots.clear(); DFS(s, 1); it = deepestrootstemp.begin(); for (it; it != deepestrootstemp.end(); it++) { deepestroots.insert(*(it)); } it = deepestroots.begin(); for (it; it != deepestroots.end(); it++) { printf("%d\n", *it); } } else { printf("Error: %d components\n", count); } }//只需至少两次DFS就行，若太多会超时，第一次DFS找出深度最大的那些点，然后从中任选一个进行 //第二次DFS，再次找深度最大的哪些点，这两次DFS所找到的点的并集就是，注意去重和排序 int main() { scanf("%d", &N); int u, v; if (N == 1) { printf("1\n"); return 0; } for (int i = 0; i < N - 1; i++) { scanf("%d %d", &u, &v); G[u - 1].push_back(v - 1); G[v - 1].push_back(u - 1); } DFSTrave(G); return 0; }