这题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;
}