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解题思路：给出n个结点（1~n）之间的n条边，问是否能构成一棵树，如果不能构成则输出它有的连通分量个数，如果能构成一棵树，输出能构成最深的树的高度时，树的根结点。如果有多个，按照从小到大输出。考察知识点：并查集，图的遍历。
代码如下：
#include<stdio.h> #include<queue> #include<vector> #include<algorithm> using namespace std; vector<int> Graph[10010]; queue<int> que; int Tree[10010]; vector<int> ans; bool visit[10010]; int tail, n; int findRoot(int x) { if(Tree[x] == -1) return x; else { int tmp = findRoot(Tree[x]); Tree[x] = tmp; return tmp; } } int findHeight(int x) { visit[x] = true; int curHeight = 0; que.push(x); que.push(-1); while(!que.empty()) { if(que.front() == -1) { curHeight ++; que.pop(); if(que.empty()) break; else que.push(-1); } int front = que.front(); tail = front; for(int i = 0; i < Graph[front].size(); i ++) { if(!visit[Graph[front][i]]) que.push(Graph[front][i]); visit[Graph[front][i]] = true; } que.pop(); } for(int i = 1; i <= n; i ++) visit[i] = false; return curHeight; } int main() { freopen("D://input.txt", "r", stdin); scanf("%d", &n); for(int i = 1; i <= n; i ++) { Tree[i] = -1; visit[i] = false; } int a, b; for(int i = 0; i < n-1; i ++) { scanf("%d%d", &a, &b); Graph[a].push_back(b); Graph[b].push_back(a); a = findRoot(a); b = findRoot(b); if(a != b) Tree[a] = b; } int count = 0; for(int i = 1; i <= n; i ++) { if(Tree[i] == -1) count ++; } if(count > 1) { printf("Error: %d components\n", count); return 0; } else { int maxHeight, root; for(int i = 1; i <= n; i ++) { if(Graph[i].size() == 1) { root = i; break; } } maxHeight = findHeight(root); while(maxHeight != findHeight(tail)) { root = tail; maxHeight = findHeight(root); } for(int i = 1; i <= n; i ++) { if(findHeight(i) == maxHeight) { ans.push_back(i); } } sort(ans.begin(), ans.end()); for(int i = 0; i < ans.size(); i ++) printf("%d\n", ans[i]); } return 0; }
