Cod sursa(job #1196817)

Utilizator howsiweiHow Si Wei howsiwei Data 9 iunie 2014 11:33:53
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int,int> II;

vector<vector<int>> adjl;

II dfs(int u, int p = -1, int level = 1) {
	II bestu = {level, u};
	for (auto v: adjl[u]) {
		if (v == p) {
			continue;
		}
		bestu = max(bestu, dfs(v, u, level+1));
	}
	return bestu;
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);
	int n;
	cin >> n;
	adjl.resize(n);
	for (int i = 0; i < n-1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adjl[u].push_back(v);
		adjl[v].push_back(u);
	}
	int diameter = dfs(dfs(0).second).first;
	printf("%d\n", diameter);
	return 0;
}