PAT-A1021 Deepest Root 题目内容及题解
A graph which is connected and acyclic can be considered a tree. The hight 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:
Error: 2 components
题目大意
一个连通的无环图可以看做一个树,而树的高度取决于根节点的选择。题目要求找到使树最高的根,如符合条件的根不唯一则找到所有这样的根并按增序输出。如所给图并不连通,则输出其连通子图数量。
解题思路
- 用查并集检查所有结点组成多少联通子图,同时用邻接表保存图,如子图数目大于1则输出子图数量并返回0值;
- 如为连通图,随便从一个节点出发进行DFS 找到最深的若干个节点;
- 从某个最深节点出发进行DFS找到最深节点,结合第二步所得即为结果;
- 返回所求结果并返回0值。
代码
#include<stdio.h>
#include<vector>
using namespace std;
#define maxn 10010
int Deepest[maxn];
int numDeep,maxDeep=-1;
vector<int> Adj[maxn];
int father[maxn];
int isroot[maxn];
int isdeep[maxn];
int n;
int findFather(int x){
int z,a;
a=x;
while(father[x]!=x){
x=father[x];
}
while(a!=x){
z=a;
a=father[a];
father[z]=x;
}
return x;
}
void Union(int a,int b){
int fa,fb;
fa=findFather(a);
fb=findFather(b);
if(fa!=fb){
father[fa]=fb;
}
}
void Init(){
int i,a,b;
scanf("%d",&n);
for(i=1;i<=n;i++){
father[i]=i;
isroot[i]=0;
isdeep[i]=0;
}
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
Adj[a].push_back(b);
Adj[b].push_back(a);
Union(a,b);
}
return;
}
void DFS(int u,int depth,int pre){
int i,v;
if(depth>maxDeep){
maxDeep=depth;
numDeep=0;
Deepest[numDeep++]=u;
}else if(depth==maxDeep){
Deepest[numDeep++]=u;
}
for(i=0;i<Adj[u].size();i++){
v=Adj[u][i];
if(v!=pre){
DFS(v,depth+1,u);
}
}
return;
}
int main(){
int nnum=0,i;
Init();
for(i=1;i<=n;i++){
isroot[findFather(i)]=1;
}
for(i=1;i<=n;i++){
nnum+=isroot[i];
}
if(nnum>1){
printf("Error: %d components\n",nnum);
}else{
DFS(1,0,0);
for(i=0;i<numDeep;i++){
isdeep[Deepest[i]]=1;
}
DFS(Deepest[0],0,0);
for(i=0;i<numDeep;i++){
isdeep[Deepest[i]]=1;
}
for(i=1;i<=n;i++){
if(isdeep[i]){
printf("%d\n",i);
}
}
}
return 0;
}
运行结果