这题 debug 的可以说是很难受了，想了半天怎么也想不出来哪里错了，oj 显示错一大片，只有少数几个对的。无奈自己写了一个复杂一点的样例，果然错了，设了两个断点，一行行看下来，突然发现自己++height 用错了，还是基础不好。++i，整体代表 height 值+1 后的结果，这一点没有问题，而且潜意识里我一般喜欢用++i，看过我 code 的朋友应该发现我，每个 for 循环用的都是++i，这是因为在具体实现时，++i 更快更省空间，因为底层中 i++需要两个 int 分别存储加之前的值和加之后的值。这些都没有错，关键是我在调用 DFS 内 for 循环中递归调用 DFS 的时候，忘记 height 对于 for 循环的下一个 DFS 来说不应该自增。换句话说，DFS 一条路走到底之后回到交叉口的时候 height 不应该改变，而在写代码的时候因为偷懒，顺手写了个++height，导致了 DFS 访问时 height 不对了。面壁去了。。。 github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：★★★☆ 关键词：无向图环的判断，树的高度，DFS

# 题目

1021: Deepest Root (25) 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

Sample Input 3: 16 1 2 2 3 2 7 4 5 5 6 5 7 7 8 7 13 7 14 8 9 8 10 11 13 12 13 14 15 14 16

Sample Output 3: 1 3 4 6 9 10 11 12 15 16

# 大意

给出 n 个节点，n-1 条边，首先判断是否是是否是树。如果是树，选择源点，使得该树的深度最大。

# 思路

1. 首先，我们来解决第一个问题，怎么判断一个图是不是树。我们知道无圈的图是树（虽然博主，圈和环傻傻分不清），那么问题就转换成如何判断一张无向图，是否存在环。几种思路：一、并查集，遍历边，若两个定点在不同集合中，则合并集合，若在同一集合中则说明有环；二、DFS。随意取一个点做源点，进行 DFS 遍历，若一次能遍历完，则说明只有一个连通分量，所以该图无环。
2. 确定树的深度，想到用一个参数 height 来记录 DFS 遍历深度，则 height 的最大值就是树的深度。
3. 如何确定使树深度最大的源点。博主是这样考虑的，先随意选一个点，作为 DFS 的源点，那么有可能是树深度最大的源点，就是这次 DFS 遍历得到最大 height 的尾结点。然后从这些可能的点出发，再进行一次 DFS，同样选择最大 height 对应的尾结点就是使得树深度最大的源点。说起来有点绕，画张图可能就好理解了。再仔细想想，满足条件的结点，不可能只有一个，起码是两个，第一次 DFS 得到的最大 height 尾结点，一定是其中一部分。
4. 具体实现的时候，还是有些复杂，图的存储使用了常规的邻接表 vector G[maxn]，可能源点存放在一个 vector 中，确定的结点还在一个 set 中，减少排序工作量。读者可以细细品一下中间一部分 code。

# code

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

const int maxn = 10010;
vector<int> G[maxn];
vector<int> temp;
set<int> s;
int n, maxheight = 0;
bool vis[maxn] = {false};

void DFS(int now, int height) {
  if (height >= maxheight) {
    if (height > maxheight) {
      temp.clear();
    }
    temp.push_back(now);
    maxheight = height;
    //      for(int i=0;i<temp.size();++i){
    //          cout<<temp[i]<<" ";
    //      }
    //      cout<<endl;
  }
  vis[now] = true;
  for (int i = 0; i < G[now].size(); ++i) {
    if (vis[G[now][i]] == false) {
      DFS(G[now][i], height + 1);  //Íò¶ñÖ®Ô´++height
    }
  }
}
int main() {
  scanf("%d\n", &n);
  int size = 0, start = 0;
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
  }
  fill(vis, vis + maxn, false);
  for (int i = 1; i <= n; ++i) {
    if (vis[i] == false) {
      DFS(i, 1);
      if (i == 1) {
        for (int j = 0; j < temp.size(); ++j) {
          s.insert(temp[j]);
          if (j == 0) start = temp[j];
        }
      }
      ++size;
    }
  }
  //    cout<<size;
  if (size > 1) {
    printf("Error: %d components", size);
  } else {
    temp.clear();
    fill(vis, vis + maxn, false);
    maxheight = 0;
    DFS(start, 1);
    for (int i = 0; i < temp.size(); ++i) {
      s.insert(temp[i]);
    }
    for (auto it = s.begin(); it != s.end(); ++it) {
      printf("%d\n", *it);
    }
  }
  return 0;
}