Cod sursa(job #1095428)

Utilizator robert_stefanRobert Stefan robert_stefan Data 30 ianuarie 2014 22:21:31
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <vector>
#include <queue>
#include <fstream>
#define IN "darb.in"
#define OUT "darb.out"
#define NMAX 100005

using namespace std;

ifstream in(IN);
ofstream out(OUT);

int n, contor[NMAX], last, diametru;

vector <int> G[NMAX];
queue  <int> coada;

bool viz[NMAX];

inline void BF(int nod)
{
	int i;
	for(i=1; i<=n; ++i)
		contor[i]=0,
		viz[i]=0;
	coada.push(nod);
	viz[nod]=1;
	contor[nod]=1;
	diametru=1;
	while(!coada.empty())
	{
		for(i=0; i<G[coada.front()].size(); ++i)
			if(!viz[G[coada.front()][i]])
			{
				coada.push(G[coada.front()][i]);
				last=G[coada.front()][i];
				contor[last]=contor[coada.front()]+1;
				diametru=contor[last];
				viz[last]=1;
			}
		coada.pop();
	}
}

int main ()
{
	int x, y, i;
	in>>n;
	for(i=1; i<n; ++i)
	{
		in>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	BF(1);
	BF(last);
	out<<diametru<<'\n';
	in.close();
	out.close();
	return 0;
}