最深的根

• 这道题首先要通过并查集确定有多少个联通块。

• 在建树的时候，因为方向不固定，所以要用无向边来建树。因此在dfs求树的深度的时候要多传一个 father 变量进去以确定其父亲，如果发现 j == father 的时候就跳过，防止循环遍历。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010, M = N * 2;

int n;
int p[N];
int e[M], ne[M], h[N], idx;

int find(int x)
{
  if (x != p[x]) p[x] = find(p[x]);
  return p[x];
}

void add(int a, int b)
{
  e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u, int father)
{
  int depth = 0;
  for (int i = h[u]; ~i; i = ne[i])
  {
      int j = e[i];
      if (j == father) continue;
      depth = max(depth, dfs(j, u) + 1);
  }

  return depth;
}

int main()
{
  memset(h, -1, sizeof h);
  for (int i = 0; i < N; i ++ ) p[i] = i;

  cin >> n;
  int cnt = n;
  for (int i = 0; i < n; i ++ )
  {
      int a, b;
      cin >> a >> b;

      int pa = find(a), pb = find(b);
      if (pa != pb)
      {
          cnt -- ;
          p[pa] = pb;
      }
      add(a, b), add(b, a);
  }

  if (cnt > 1) printf("Error: %d components\n", cnt);
  else
  {
      vector<int> nodes;
      int max_depth = 0;
      for (int i = 1; i <= n; i ++ )
      {
          // 第二个参数是其父亲。因为是双向边，防止回头
          int depth = dfs(i, -1);
          if (depth > max_depth)
          {
              max_depth = depth;
              nodes.clear();
              nodes.push_back(i);
          }
          else if (depth == max_depth)
              nodes.push_back(i);
      }

      for (auto i : nodes) printf("%d\n", i);
  }

  return 0;
}