Cod sursa(job #1335851)

Utilizator ooptNemes Alin oopt Data 5 februarie 2015 23:14:25
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
// darb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define NMax 100005
#define pb push_back
#define mp make_pair
using namespace std;

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

int n;
vector<int> V[NMax];
int lastNode;
int val[NMax];
deque<int> C;
int diametru;

void bfs(int node) {
	memset(val, 0, sizeof(val));
	val[node] = 1;
	C.pb(node);
	while (!C.empty()) {
		int el = C[0];
		C.pop_front();
		for (unsigned i=0;i<V[el].size();i++) {
			int vecin = V[el][i];
			if (val[vecin] == 0) {
				val[vecin] = val[el] + 1;
				lastNode = vecin;
				diametru = val[vecin];
				C.pb(vecin);
			}
		}
	}
}

void read() {
	f>>n;
	for (int i=1;i<n;i++) {
		int a, b;
		f>>a>>b;
		V[a].pb(b);
		V[b].pb(a);
	}
}

int main() {
	
	read();
	bfs(1);
	bfs(lastNode);
	g<<diametru<<endl;

	f.close(); g.close();
	return 0;
}