Boj 1167) 트리의지름

GraphTheory

백준 1167

설명

트리의 지름을 구하는 가장 간단한 방법은 임의의 점을 하나 두고 제일 먼 점을 구한뒤, 그 점부터 가장 먼점의 길이임.

트리의 지름을 구성하는 정점 두개를 지름으로 하는 원 을 그리면 쉽게 이해할 수 있음.

나머지 정점은 원 내부에 들어가게 되는데, 모든 정점에서 그곳에서 시작해서 가장 먼점은 지름은 만드는 정점임.

그 점에서 가장 먼점은 당연히 지름을 구성하는 또 다른 정점이게 됨

시간 복잡도

O(n)

코드

struct Line { int to, w; };
vector<Line> lines[100001];

int farest_idx, farest_weight;
void DFS(int cur, int from, int weight = 0)
{
	for (auto line : lines[cur])
	{
		if (line.to == from) continue;
		DFS(line.to, cur, weight+line.w);
	}

	if (lines[cur].size() == 1)
	{
		if (farest_weight < weight)
		{
			farest_idx = cur;
			farest_weight = weight;
		}
	}
}

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		static int from;
		cin >> from;
		while (1)
		{
			static int to, w;
			cin >> to;
			if (to == -1) break;
			auto& l = lines[from].emplace_back();
			cin >> l.w;
			l.to = to;
		}
	}
	
	farest_weight = -1;
	DFS(1, -1);
	farest_weight = -1;
	DFS(farest_idx, -1);
	
	cout << farest_weight;
}