木の直径

コード例

#include <bits/stdc++.h>

using namespace std;
using P = pair<int, int>;
const int INF = 1000000000;

int main() {
  int n = 7;
  vector<vector<int>> edge = {{1}, {0, 2, 4}, {1, 3}, {2}, {1, 5}, {4, 6}, {5}};

  auto bfs = [&](int start) -> P {
    vector<int> dist(n, INF);
    dist[start] = 0;

    queue<int> q;
    q.push(start);

    while (!q.empty()) {
      int cur = q.front();
      q.pop();

      for (auto next : edge[cur]) {
        if (dist[next] != INF) continue;
        dist[next] = dist[cur] + 1;
        q.push(next);
      }
    }

    int max_i = 0;
    int max_dist = 0;
    for (int i = 0; i < n; i++) {
      if (max_dist < dist[i]) {
        max_dist = dist[i];
        max_i = i;
      }
    }

    return {max_i, max_dist};
  };

  cout << bfs(bfs(0).first).second << endl;
}

解説/アルゴリズム

木の頂点間の最大距離を木の直径と呼ぶ。

任意の頂点から一番離れた場所にある頂点を調べ、その頂点から一番離れた頂点までの距離が木の直径になる。

探索は幅優先探索や深さ優先探索を利用する。