Cod sursa(job #1703084)

Utilizator Gabiap2015Apostol Gabriel Gabiap2015 Data 16 mai 2016 10:16:14
Problema Diametrul unui arbore Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include "iostream"
#include "fstream"
#include "vector"
#include "queue"
#include <string.h>
using namespace std;

#define MAX 100000
ifstream darb_in("darb.in");
ofstream darb_out("darb.out");

vector <int> graf[MAX];
queue <int> coada;
int n, distanta[MAX], ver[MAX], last, diametru;

void bfs(int nod_start)
{
	memset(distanta, 0, MAX);
	memset(ver, 0, MAX);
	coada.push(nod_start);
	distanta[nod_start] = 1;
	ver[nod_start] = 1;
	int curent;
	while (!coada.empty())
	{
		curent = coada.front();
		for (int i = 0; i<graf[curent].size(); i++)
		{
			if (ver[graf[curent][i]] == 0)
			{
				coada.push(graf[curent][i]);
				distanta[graf[curent][i]] = distanta[curent] + 1;
				ver[graf[curent][i]] = 1;
				diametru = distanta[graf[curent][i]];
				last = graf[curent][i];
			}
		}
		coada.pop();
	}
}


int main()
{
	int x, y;
	darb_in >> n;
	for (int i = 0; i < n - 1; i++)
	{
		darb_in >> x >> y;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	bfs(1);
	bfs(last);
	/*
	cout << "diametru arborelui: " << diametru << endl;
	cout << "raza arborelui: " << diametru / 2 << endl;
	cout << "Centrul arborelui: " << endl;
	
	for (int i = 1; i <= n; i++)
	{
		if (distanta[i] == diametru / 2)
			cout <<"Nodul: "<< i << endl;
	}
	*/
	darb_out << diametru;
	return 0;
}