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:
51 21 31 42 5
Sample Output 1:
345
Sample Input 2:
51 31 42 53 4
Sample Output 2:
Error: 2 components 终于不是模拟题了，舒服。。。 大概题意就是----给你一组数据，要么是树，要么就是非连通图， 如果是树，你就把最远距离的端点输出来，如果不是树，就输出它分成了几个部分。 题目挺好的。 题解如下：26ms
1 #include2 #define N 10050 3 using namespace std; 4 int n, pos = 0; 5 vector v[N]; 6 int vis[N], val[N]; 7 int max_len = 0, id = 0; 8 set s; 9 set ::iterator it;10 bool flag = false;11 void dfs(int x){12 vis[x] = 1;13 for(int i = 0 ; i < v[x].size(); i++){14 int k = v[x][i];15 if(vis[k] == 0)16 dfs(k);17 }18 }19 void dfs1(int x,int len){20 vis[x] = 1;21 if(len > max_len){22 max_len = len;23 id = x;24 }25 for(int i = 0; i < v[x].size(); i++){26 int k = v[x][i];27 if(vis[k] == 0){28 dfs1(k, len+1);29 }30 }31 }32 33 void dfs2(int x,int len){34 vis[x] = 1;35 if(len == max_len){36 s.insert(x);37 val[x] = 1;38 flag = true;39 }40 for(int i = 0; i < v[x].size(); i++){41 int k = v[x][i];42 if(vis[k] == 0){43 dfs2(k, len+1);44 }45 }46 }47 48 int main(){49 cin >> n;50 if(n == 1){51 cout << "1" << endl;52 return 0;53 }54 int x, y;55 for(int i = 1; i < n; i++){56 cin >> x >> y;57 v[x].push_back(y);58 v[y].push_back(x);59 }60 memset(vis,0,sizeof(vis));61 for(int i = 1; i <= n; i++){62 if(vis[i] == 0){63 dfs(i);64 pos++;65 }66 }67 if(pos > 1){68 printf("Error: %d components\n", pos);69 }else{70 memset(vis,0,sizeof(vis));71 dfs1(1,0);72 memset(vis,0,sizeof(vis));73 dfs1(id,0);74 for(int i = 1; i <= n; i++){75 if(v[i].size() == 1 && val[i] == 0){76 memset(vis,0,sizeof(vis));77 dfs2(i,0);78 if(flag){79 flag = false;80 s.insert(i);81 val[i] = 1;82 }83 }84 }85 // cout << "****" <