Cod sursa(job #1502307)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 14 octombrie 2015 16:07:29
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
#include <bitset>

#define NMAX 100005

using namespace std;


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

int d[NMAX];

bitset <NMAX> viz;
vector <int> G[NMAX];

int maxNod, dmax;
void DF(int nod)
{
	viz[nod] = 1;
	for (vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
		if (!viz[*it])
		{
			d[*it] = d[nod] + 1;
			if (d[*it] > dmax) 
			{
				dmax = d[*it];
				maxNod = *it;
			}
			DF(*it);
		}
}

int main()
{
	int x, y;
	int n;
	fin >> n;
	for (int i = 1; i < n; ++i)
	{
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	DF(1);
	viz.reset();
	memset(d, 0, sizeof(d));
	DF(maxNod);

	fout << dmax + 1  << '\n';
	return 0;
}