Cod sursa(job #2258490)

Utilizator filicriFilip Crisan filicri Data 11 octombrie 2018 15:44:10
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define lim 100004
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
vector <int> muc[lim];
queue <int> q;
int n,x,y,maxim=-1,nod,poz=-1;
int lant[lim];
int frunze[lim];
int main()
{
	f>>n;
	for (int i=1;i<=n-1;i++)
	{
		f>>x>>y;
		muc[x].push_back(y);
		muc[y].push_back(x);
	}
	q.push(1);
	while (!q.empty())
	{
		nod=q.front();
		q.pop();
		for (int i=0;i<muc[nod].size();i++)
			if (lant[muc[nod][i]]==0)
			{
				lant[muc[nod][i]]=lant[nod]+1;
				if (lant[muc[nod][i]]>maxim) 
				{
					maxim=lant[muc[nod][i]];
					poz=muc[nod][i];
				}
				q.push(muc[nod][i]);
			}
	}
	maxim=-1;
	q.push(poz);
	while (!q.empty())
	{
		nod=q.front();
		q.pop();
		for (int i=0;i<muc[nod].size();i++)
			if (frunze[muc[nod][i]]==0)
			{
				frunze[muc[nod][i]]=frunze[nod]+1;
				if (frunze[muc[nod][i]]>maxim) maxim=frunze[muc[nod][i]];
				q.push(muc[nod][i]);
			}
	}
	g<<maxim+1;
	f.close();
	g.close();
	return 0;
}