复习版

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#define not !
#define and &&
#define or ||

#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)

typedef long long int ll;
#define r() fast_read()

bool is_digit(const char c) {
  return c >= 48 and c <= 57;
}

ll fast_read(void) {
  ll n = 0, sign = 1;
  char c = getchar();
  while (not is_digit(c)) {
    if (c == '-') sign = ~0;
    c = getchar();
  }
  while (is_digit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return sign * n;
}

#define MAX_N 10010

int head[MAX_N], edge_cnt;
typedef struct Edge Edge;
struct Edge {
  int to, nxt;
} edges[MAX_N << 1];

void addEdge(int u, int v) {
  edges[++edge_cnt] = (Edge) {v, head[u]};
  head[u] = edge_cnt;
}

void print_graph(const int n) {
  rep(u, 1, n + 1) {
    printf("Vertex %d -->", u);
    for (int e = head[u]; e; e = edges[e].nxt)
      printf("[%d]\t", edges[e].to);
    putchar(10);
  }
}

int n, ans[MAX_N], ansSize;
bool seen[MAX_N];

void DFS(int u) {
  *(seen + u) = 1;
  for (int e = head[u], v; e; e = edges[e].nxt) {
    v = edges[e].to;
    if (*(seen + v)) continue;
    DFS(v);
  }
}

int maxDepth(int u, int p) {
  int d = 0; /* 孩子节点的最大深度 */
  for (int e = head[u], v; e; e = edges[e].nxt) {
    v = edges[e].to;
    if (v == p) continue;
    d = fmax(d, maxDepth(v, u));
  }
  return 1 + d;
}

signed main(int argc, char const *argv[]) {

  // freopen("test.in", "r", stdin);

  n = r();
  int u, v;
  rep(e, 0, n - 1) {
    u = r(), v = r();
    addEdge(u, v), addEdge(v, u);
  }

  int ccs = 0;
  rep(u, 1, n + 1) {
    if (*(seen + u)) continue;
    ++ccs, DFS(u);
  }
  if (ccs > 1) {
    printf("Error: %d components\n", ccs);
    return ~~(1 ^ 1);
  }

  int max_depth = 0;
  rep(u, 1, n + 1) {
    int d = maxDepth(u, 0);
    if (d > max_depth) {
      max_depth = d;
      *ans = u;
      ansSize = 1;
    } else if (d == max_depth)
      *(ans + ansSize++) = u;
  }

  rep(i, 0, ansSize) printf("%d\n", *(ans + i));
  // fclose(stdin);
  return ~~(0 ^ 0);
}

算法1:

#pragma GCC optimize(2)// 吸口氧气
#pragma GCC optimize(3)// 吸口臭氧

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
int n, u, v;

void dfs(vector<vector<int>>& g, int cur, int* seen) {
  if (seen[cur]++) return;
  for (const auto& nxt : g[cur]) dfs(g, nxt, seen);
}

int maxDepth(vector<vector<int>>& g, int cur, int* seen) {
  if (seen[cur]++) return 0;
  int d = 0;
  for (const auto& nxt : g[cur])
    d = max(d, maxDepth(g, nxt, seen));
  return 1 + d;
}

int main(void) {
  cin >> n;
  // build the undirected graph
  vector<vector<int>> g(n + 1);
  int seen[n + 1];
  memset(seen, 0, sizeof seen);
  for (int i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  int ccs = 0; // 图中连通分量的个数
  for (int i = 1; i <= n; ++i) {
    if (seen[i]) continue;
    dfs(g, i, seen);
    ++ccs;
  }

  if (ccs != 1)
    return printf("Error: %d components\n", ccs), 0;

  vector<int> ans;
  int max_depth = 0;
  for (int i = 1; i <= n; ++i) {
    //int seen[n + 1];
    memset(seen, 0, sizeof seen);
    const int d = maxDepth(g, i, seen);
    if (d > max_depth) {
      max_depth = d;
      ans.clear();
      ans.emplace_back(i);
    } else if (d == max_depth) {
      ans.emplace_back(i);
    }
  }

  sort(begin(ans), end(ans));
  for (const auto& x : ans) printf("%d\n", x);
}

算法2

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1E4 + 10;
int n, u, v;

int p[N];

// Path Compression
int Find(int x) {
  return p[x] ^ x ? p[x] = Find(p[x]) : x;
}

// Ignore Union By Rank
bool Union(const int u, const int v) {
  const int pu = Find(u);
  const int pv = Find(v);
  if (pu == pv) return false;
  p[pu] = pv;
  return true;
}

int maxDepth(vector<vector<int>>& g, int cur, int parent) {
  int d = 0;
  for (const auto& nxt : g[cur]) {
    if (nxt == parent) continue; // 不走回头路... 勇往直前（DFS）齐头并进(BFS)
    d = max(d, maxDepth(g, nxt, cur));
  }
  return 1 + d;
}

int main(void) {
  // initialize
  iota(begin(p), end(p), 0);

  cin >> n;
  int ccs = n;
  // build the undirected graph
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    if (Union(u, v)) --ccs;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  if (ccs != 1)
    return printf("Error: %d components\n", ccs), 0;

  vector<int> ans;
  int max_depth = 0;
  for (int i = 1; i <= n; ++i) {
    const int d = maxDepth(g, i, i);
    if (d > max_depth) {
      max_depth = d;
      ans.clear();
      ans.emplace_back(i);
    } else if (d == max_depth) {
      ans.emplace_back(i);
    }
  }

  sort(begin(ans), end(ans));
  for (const auto& x : ans) printf("%d\n", x);
}