Cod sursa(job #1617411)

Utilizator artasRares Ghioc artas Data 27 februarie 2016 13:30:23
Problema Diametrul unui arbore Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int viz[100001], n,j;
struct pizza
{
	int a, b;
}m[100001];
bool cmp(pizza a, pizza b)
{
	return a.a < b.a;
}
int bnrs(int x, int in, int sf)
{
	int mij = (in + sf) / 2;
	if (m[mij].a == x)return mij;
	if (m[mij].a > x)sf = mij - 1;
	else in = mij + 1;
	return bnrs(x, in, sf);
}
void dfs(int x, int ad)
{
	int i;
	viz[x] = ad;
	i = bnrs(x, 1, j);
	while (m[i - 1].a == m[i].a)i--;
	for (; m[i].a == x; i++)
	{
		if (!viz[m[i].b])
			dfs(m[i].b, ad + 1);
	}
}
int main()
{
	int i=0, x, y,mx=0,ind;
	f >> n;
	while (f >> x >> y)
	{
		j++;
		m[j].a = x;
		m[j].b = y;
		j++;
		m[j].a = y;
		m[j].b = x;
	}
	sort(&m[1], &m[j + 1], cmp);
	dfs(1, 1);
	for (i = 1; i <= n; i++)
		if (viz[i] > mx)
		{
			mx = viz[i];
			ind = i;
		}
	for (i = 1; i <= n; i++)viz[i] = 0;
	dfs(ind, 1);
	for (i = 1; i <= n; i++)
		if (viz[i] > mx)mx = viz[i];
	g << mx;
}