Cod sursa(job #1105941)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 12 februarie 2014 11:42:59
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

int N, R, D[100005];
vector<int> G[100005];
queue<int> Q;

int BFs(const int &X) {
	int mx = 0, ps = 0;
	
	while (Q.size())
		Q.pop();
	for (int i = 1; i <= N; ++i)
		D[i] = 0;
	
	Q.push(X); D[X] = 1;
	for (; Q.size(); Q.pop()) {
		int ret = Q.front();
		for (vector<int>::iterator i = G[ret].begin(); i != G[ret].end(); ++i) {
			if (!D[*i]) {
				D[*i] = D[ret] + 1;
				Q.push(*i);
				if (mx < D[*i]) {
					mx = D[*i];
					ps = *i;
				}
			}
		}
	}
	
	return ps;
}

int main() {
	fin >> N;
	
	for (int i = 1; i < N; ++i) {
		int X, Y;
		fin >> X >> Y;
		R = R - Y;
		G[X].push_back(Y);
		G[Y].push_back(X);
	}
	
	fout << D[BFs(BFs(1))] << '\n';
	fin.close();
	fout.close();
}