Cod sursa(job #2141373)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 24 februarie 2018 12:10:49
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");

vector< int > G[100010];

pair< int, int > DFS(int nod, int tata) {
	pair< int, int > ans(nod, 0);

	for(auto vecin: G[nod]) {
		if(vecin == tata) {
			continue;
		}

		pair< int, int > aux = DFS(vecin, nod);
		if(aux.second + 1 > ans.second) {
			ans.second = aux.second + 1;
			ans.first = aux.first;
		}
	}

	return ans;
}

int main() {

	int n; in >> n;

	for(int i = 1; i < n; ++i) {
		int x, y; in >> x >> y;

		G[x - 1].push_back(y - 1);
		G[y - 1].push_back(x - 1);
	}

	pair< int, int > frunza = DFS(0, 0);
	pair< int, int > ans = DFS(frunza.first, frunza.first);

	out << ans.second + 1 << '\n';

	in.close(); out.close();

	return 0;
}