Cod sursa(job #1466177)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 28 iulie 2015 18:45:14
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

pair<int, int> furthest(const vector<vector<int> > arb, const int start){
	vector<int> dist(arb.size(), -1);
	dist[start] = 1;
	queue<int> de_viz;
	de_viz.push(start);
	pair<int, int> rez(0, 1);
	while(!de_viz.empty()){
		const int cur = de_viz.front();
		de_viz.pop();

		if(rez.second < dist[cur]){
			rez.first = cur;
			rez.second = dist[cur]; }
		for(const auto next : arb[cur]){
			if(dist[next] == -1){
				dist[next] = dist[cur]+1;
				de_viz.push(next); } } }
	return rez; }

int main(){
	ifstream f("darb.in");
	ofstream g("darb.out");
	int n;
	f >> n;
	vector<vector<int> > arb(n);
	for(int i = 0, a, b; i < n-1; ++i){
		f >> a >> b;
		--a, --b;
		arb[a].push_back(b);
		arb[b].push_back(a); }
	g << furthest(arb, furthest(arb, 0).first).second;
	return 0; }