Cod sursa(job #1961229)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 10 aprilie 2017 23:09:47
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int N = 100005; 
const int inf = (1 << 29);

int n;
vector<int> vecini[N];
int distante[N];

void citire()
{
	scanf("%d", &n);

	int tmp1, tmp2;

	for(int i = 0; i < n - 1; i++)
	{
		scanf("%d %d", &tmp1, &tmp2);

		tmp1--;
		tmp2--;

		vecini[tmp1].push_back(tmp2);
		vecini[tmp2].push_back(tmp1);
	}

	for(int i = 0; i < n; i++)
	{
		distante[i] = inf;
	}
}

void initializareDistante()
{
	for(int i = 0; i < n; i++)
	{
		distante[i] = inf;
	}
}

void bfs(int a)
{
	queue<int> Q;	
	
	Q.push(a);
	distante[a] = 0;

	while(Q.empty() == false)
	{
		int x = Q.front(); 
		Q.pop();

		int l = vecini[x].size();

		for(int i = 0; i < l; i++)
		{
			if(distante[vecini[x][i]] > distante[x] + 1)
			{
				distante[vecini[x][i]] = distante[x] + 1;
				Q.push(vecini[x][i]);
			}
		}
	}
}

void solve()
{
	bfs(0);	

	int start;
	int max = 0;

	for(int i = 0; i < n; i++)
	{
		if(distante[i] > max)
		{
			max = distante[i];
			start = i;
		}
	}

	initializareDistante();
	bfs(start);

	for(int i = 0; i < n; i++)
	{
		if(distante[i] > max)
		{
			max = distante[i];
			start = i;
		}
	}

	printf("%d", max + 1);
}

int main()
{
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);

	citire();
	solve();

	return 0;
}