003.md

003 - Longest Circular Road (★4)

解答

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // std::pair
#include <algorithm> // std::max_element()
#include <iterator> // std::distance()

// 木において, 頂点 i から最も遠い頂点を探し, { （グラフ上の）距離, そのインデックス } を返す
std::pair<int, int> GetFarthestFrom(int i, const std::vector<std::vector<int>>& graph)
{
	std::vector<int> distances(graph.size(), -1);

	// 幅優先探索
	{
		std::queue<int> q;
		q.push(i);

		distances[i] = 0;

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

			for (const auto& to : graph[from])
			{
				if (distances[to] == -1)
				{
					distances[to] = (distances[from] + 1);
					q.push(to);
				}
			}
		}
	}

	// 最大の要素へのイテレータ
	const auto it = std::max_element(distances.begin(), distances.end());

	// 最も遠い頂点のインデックス
	const int index = std::distance(distances.begin(), it);

	// 最も遠い頂点までの（グラフ上の）距離
	const int distance = *it;

	return{ index, distance };
}

// 木の直径を求める
int GetDiameter(const std::vector<std::vector<int>>& graph)
{
	const auto [index, distance] = GetFarthestFrom(0, graph);
	const auto [index2, distance2] = GetFarthestFrom(index, graph);
	return distance2;
}

int main()
{
	// N 個の都市
	int N;
	std::cin >> N;

	// N 頂点のグラフ
	std::vector<std::vector<int>> graph(N);
	for (int i = 0; i < (N - 1); ++i)
	{
		int a, b;
		std::cin >> a >> b;
		graph[a - 1].push_back(b - 1);
		graph[b - 1].push_back(a - 1);
	}

	// (木の直径 + 1) が答え
	const int a = (GetDiameter(graph) + 1);

	// 解答を出力
	std::cout << a << '\n';
}