Cod sursa(job #2335472)

Utilizator Alex03Runcan Alexandru Alex03 Data 4 februarie 2019 10:02:48
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define MAX_N 1000001
using namespace std;
ifstream fin ("darb.in"); ofstream fout ("darb.out");

vector<int> nod[MAX_N];
queue<int> coada;
int n, contor[MAX_N], viz[MAX_N], last, diametru;

void BFS(int plecare)
{
	memset (contor, 0, MAX_N);
	memset (viz, 0, MAX_N);
	coada.push(plecare);
	contor[plecare] = 1;
	viz[plecare] = 1;
	int i, el;
	while (!coada.empty())
	{
		el = coada.front();
		for (i = 0; i < nod[el].size(); i++)
		{
			if (viz[nod[el][i]] == 0)
			{
				coada.push(nod[el][i]);
				contor[nod[el][i]] = contor[el] + 1;
				viz[nod[el][i]] = 1;

				diametru = contor[nod[el][i]];
				last = nod [el][i];
			}
		}
		coada.pop();
	}
}

void citire()
{
	int i, a, b;
	fin >> n;
	for (i = 0; i < n - 1; i++)
	{
		fin >> a >> b;
		nod[a].push_back(b);
		nod[b].push_back(a);
	}
}

int main()
{
	citire();
	BFS(1);
	BFS(last);
	fout << diametru;
	return 0;
}