Cod sursa(job #1244430)

Utilizator federerUAIC-Padurariu-Cristian federer Data 17 octombrie 2014 14:54:12
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#define Nmax 100010
using namespace std;

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

int N, i, x, y, nod1, diametru, nivel[Nmax];
vector<int>G[Nmax];
queue<int>Q;
bitset<100000>viz;
void BFS(int nod)
{
	int x;
	Q.push(nod);
	viz.set().flip();
	nivel[nod] = 1;
	while (!Q.empty())
	{
		x = Q.front();
		Q.pop();
		for (int i = 0; i< G[x].size(); ++i)
			if (!viz[G[x][i]])
		{
			nivel[G[x][i]] = nivel[x] + 1;
			viz[G[x][i]] = 1;
			Q.push(G[x][i]);
		}
	}
	nod1 = x;
	diametru = nivel[nod1];
}

int main()
{
	fin >> N;
	for (i = 1; i < N; ++i)
	{
		fin >> x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	BFS(1);
	BFS(nod1);
	fout << diametru << '\n';
	return 0;
}