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 <iostream> #include <vector> #include <queue> using namespace std; vector<int> adj[];
int visit[];
int Tree[];
int root[];
int MM[];
int num;
int getroot(int x) { if(Tree[x]==-) return x; else {
int tem=getroot(Tree[x]);
Tree[x]=tem;
return tem;
} } void DFS(int x,int d) {
visit[x]=;
int i;
for(i=;i<adj[x].size();i++)
{ if(visit[adj[x][i]]==)
DFS(adj[x][i],d+);
}
root[num++]=d;
} int main() {
int n,a,b,i,j;
while(cin>>n)
{
for(i=;i<=n;i++)//初始化
{
Tree[i]=-;
adj[i].clear();
}
for(i=;i<n-;i++)
{
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
a=getroot(a);//并查集
b=getroot(b);
if(a!=b)
{
Tree[a]=b;
}
}
int count=;//极大连通图个数
for(i=;i<=n;i++)
{
if(Tree[i]==-) count++;
}
if(count!=)
{
cout<<"Error: "<<count<<" components"<<endl;//不是树
}
else
{
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)//每次查找都要初始化
visit[j]=;
num=;
DFS(i,);
MM[i]=;
for(j=;j<num;j++)
{
if(MM[i]<root[j])
MM[i]=root[j];
}
}
int max=;
for(i=;i<=n;i++)
{
if(max<MM[i])
max=MM[i];
}
for(i=;i<=n;i++)
{
if(max==MM[i])
cout<<i<<endl;
}
}
}
return ;
}