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 5Sample Output 1:
3 4 5Sample Input 2:
5 1 3 1 4 2 5 3 4Sample Output 2:
Error: 2 components
题意：给出一个无环图，求某个节点使得以它为根节点组成一棵树使得这棵树的深度达到最大。
思路：因为节点数大于10000而边数小于节点数是一个稀疏图，使用邻接矩阵存储的话内存会超限（我已经试过了），所以选用邻接表存储，邻接表的话使用vector比较合适。判断是否连通由几部分组成时选用并查集，之后我使用bfs来搜索最深的节点。
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int n,maxh;
vector<int> vec[10005];
int bin[10005],h[10005],vis[10005],dist[10005];
queue<int> st;
int findx(int x)
{
int k,j,r;
r=x;
while(r!=bin[r])
{
r=bin[r];
}
k=x;
while(k!=r)
{
j=bin[k];
bin[k]=r;
k=j;
}
return r;
}
void mergex(int x,int y)
{
int fx=findx(x);
int fy=findx(y);
if(fx!=fy)
{
bin[fx]=fy;
}
return ;
}
int bfs(int pos)
{
int height=0;
while(!st.empty())
st.pop();
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
st.push(pos);
vis[pos]=1;
int i,j,k;
while(!st.empty())
{
k=st.front();
st.pop();
for(i=0;i<vec[k].size();i++)
{
if(!vis[vec[k][i]])
{
dist[vec[k][i]]=dist[k]+1;
if(dist[vec[k][i]]>height) height=dist[vec[k][i]];
st.push(vec[k][i]);
vis[vec[k][i]]=1;
}
}
}
if(height>maxh) maxh=height;
return height;
}
int main()
{
int i,j,k,x,y;
cin>>n;
for(i=1;i<=n;i++) bin[i]=i;
for(i=1;i<n;i++)
{
cin>>x>>y;
vec[x].push_back(y);
vec[y].push_back(x);
mergex(x,y);
}
int component=0;
for(i=1;i<=n;i++)
if(bin[i]==i) component++;
if(component>1)
{
cout<<"Error: "<<component<<" components"<<endl;
}
else
{
maxh=0;
for(i=1;i<=n;i++)
{
h[i]=bfs(i);
}
for(i=1;i<=n;i++)
{
if(h[i]==maxh) cout<<i<<endl;
}
}
return 0;
}
原文：http://blog.csdn.net/zju_ziqin/article/details/19763755