PAT甲级1021 Deepest Root (25分)|C++实现

一、题目描述

原题链接
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:

​​Output Specification:

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

二、解题思路

这道题题意很简单，给我们一系列的顶点和边，如果可以构成一棵树，则输出这棵树使高度最高时的根节点，如果结果不唯一，按编号从小到大输出。若所有的节点不构成一棵树，则输出连通分量的个数。

我们可以定义一个全局的set<int> s来存放所有符合条件的根节点，因为在set这个STL中，所有的数字会自动排序，而且可以去除重复的数字。十分方便。显然，要计算树的深度，我们可以用dfs，每一次更新深度height，然而，只用一次dfs是不能确定最大深度的，我们所能得到的最大深度与我们选取的起点有关。事实上这很好理解，如下图：

但是，我们以经过一次dfs得到的深度最大的点为起点，再次进行一次dfs就一定可以找到深度最大的点。深度最大的点也可以作为根节点。将这些点都存入s中，用auto遍历输出即可。

三、AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int N, maxheight = 0;   //节点个数N，记录最大高度
vector<vector<int> > Adj;   //邻接表
bool visit[10010];  //标志是否已经访问过
set<int> s; //存放结果
vector<int> temp;   //存放最大高度相同的节点
void dfs(int node, int height)  //深度优先搜索
{
  if(height > maxheight)
  {
    temp.clear();
    temp.push_back(node);
    maxheight = height;
  }
  else if(height == maxheight)	temp.push_back(node);
  visit[node] = true;
  for(int i=0; i<Adj[node].size(); i++)
  {
    if(!visit[Adj[node][i]])	dfs(Adj[node][i], height+1);
  }
}
int main()
{
  int tmp1, tmp2, cnt = 0, s1 = 0;
  scanf("%d", &N);
  Adj.resize(N+1);
  for(int i=0; i<N-1; i++)
  {
    scanf("%d%d", &tmp1, &tmp2);
    Adj[tmp1].push_back(tmp2);
    Adj[tmp2].push_back(tmp1);
  }
  for(int i=1; i<=N; i++)
  {
    if(!visit[i])
    {
      dfs(i, 1);
      if(i==1)
      {
        if(temp.size() != 0)	s1 = temp[0];
        for(int j=0; j<temp.size(); j++)
          s.insert(temp[j]);
      }
      cnt++;
    }
  }
  if(cnt >= 2)
    printf("Error: %d components", cnt);
  else
  {
    temp.clear();
    maxheight = 0;
    fill(visit, visit+10010, false);
    dfs(s1, 1);
    for(int i=0; i<temp.size(); i++)
      s.insert(temp[i]);
    for(set<int>::iterator it = s.begin(); it!=s.end(); it++)
      printf("%d\n", *it);
  }
  return 0;
}