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 (≤10 4 ) 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: #include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; #define MAX 10001 int n; //图节点个数 vector<std::vector<int> > v; //稀疏图用邻接表 int vis[MAX] = {0}; //标记 int d=0; //路径最深值 std::vector<int> depth[10001]; //最深为n-1，所以以深度为下标存储第i深时对应的根结点 void dfs(int x){ //求是否连通图 vis[x] = 1; for (int i = 0; i < v[x].size(); ++i) { if(!vis[v[x][i]]){ dfs(v[x][i]); } } } void dfs2(int x,int deep){ //cout<<x<<' '<<v[x].size()<<deep<<endl; vis[x] = 1; d = max(d,deep); //无向图直接求最深，又想图可以在v[x].size()==0时比啊表示叶子结点，无向图不行 for (int i = 0; i < v[x].size(); ++i) { if(!vis[v[x][i]]){ dfs2(v[x][i],deep+1); } } } int main(int argc, char const *argv[]) { cin>>n; v.resize(n+1); for (int i = 0; i < n-1; ++i) { int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } int cnt = 0; for (int i = 1; i <= n; ++i) { if(!vis[i]){ dfs(i); cnt++; } } if(cnt > 1) //连通分量的个数，此时不存在最深根 printf("Error: %d components",cnt); else{ //强连通 for (int i = 1; i <=n ; ++i) { d = 0; fill(vis,vis+MAX,0); dfs2(i,0); depth[d].push_back(i); //cout<<d<<endl; } int Max = n; for (int i = n; i >= 0 ; i--) { if(depth[i].size()){ //找到最深的深度 Max=i; //cout<<Max<<endl; break; } } for (int i = 0; i < depth[Max].size(); ++i) //遍历输出 { cout<<depth[Max][i]<<endl; } } return 0; }