Pat(Advanced Level)Practice-1021(Deepest Root)
Pat1021代码
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
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#define MAX 10005
using namespace std;
int dis[MAX];
vector<int> adj[MAX];
int parent[MAX];
int n;
int Find(int x)
{
int p=x;
while(p!=parent[p])
p=parent[p];
return p;
}
void Union(int x,int y)
{
int fx,fy;
fx=Find(x);
fy=Find(y);
if(fx!=fy)
parent[fx]=fy;
}
int BFS(int start)
{
for(int i=1;i<=n;i++)
dis[i]=-1;
queue<int> q;
q.push(start);
dis[start]=0;
int maxdis=0;
while(!q.empty())
{
int cur=q.front();
for(int i=0;i<adj[cur].size();i++)
{
int temp=adj[cur][i];
if(dis[temp]<0)
{
q.push(temp);
dis[temp]=dis[cur]+1;
if(dis[temp]>maxdis)
maxdis=dis[temp];
}
}
q.pop();
}
return maxdis;
}
int main(int argc,char *argv[])
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
parent[i]=i;
for(i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
adj[x].push_back(y);
adj[y].push_back(x);
Union(x,y);
}
int count=0;
for(i=1;i<=n;i++)
if(parent[i]==i)
count++;
if(count>1)
printf("Error: %d components\n",count);
else
{
map<int,int> m;
int max=BFS(1);
int index,first=1;
for(i=1;i<=n;i++)
{
if(dis[i]==max&&first)
{
index=i;
m[i]++;
first=0;
}
else if(dis[i]==max)
m[i]++;
}
max=BFS(index);
dis[i]=max;
for(i=1;i<=n;i++)
if(dis[i]==max)
m[i]++;
map<int,int>::iterator it;
for(it=m.begin();it!=m.end();it++)
printf("%d\n",it->first);
}
return 0;
}