Cod sursa(job #1706325)

Utilizator srefan1Oncioiu Stefan srefan1 Data 22 mai 2016 11:23:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<queue>

using namespace std;


int n, frunza, lungime = -100;
//int coada[1000];
//int nc;
vector < vector <int> >graph;
vector<int>visited;

void BFS(int vertex)
{ //for(int i=0;i<100;i++)
	// coada[100]=0;
	//nc=0;
	if ((vertex<0) || (vertex>n - 1))
	{
		return;
	}
	queue <int> q;
	int element;
	q.push(vertex);
	visited[vertex] = 0;

	while (!q.empty())
	{
		element = q.front();
		for (unsigned int i = 0; i<graph[element].size(); i++)
		{
			if (visited[graph[element][i]] == -1)
			{ //coada[nc]=graph[element][i];
				//nc++;
				q.push(graph[element][i]);
				visited[graph[element][i]] = visited[element] + 1;
				if (lungime<visited[graph[element][i]])
					lungime = visited[graph[element][i]];

			}
		}
		q.pop();
		frunza = element;
	}
}


int main()
{
	int x, y;
	ifstream f("darb.in");
	ofstream g("darb.out");
	f >> n;
	graph.resize(n);
	visited.resize(n, -1);

	for (int i = 0; i<n - 1; i++)

	{
		f >> x >> y;
		x = x - 1;
		y = y - 1;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	BFS(0);
	visited.clear();
	visited.resize(n, -1);
	BFS(frunza);
	g << lungime + 1 << endl;
	/*g<<"Raza arbore: "<<(lungime+1)/2<<endl;
	g<<"Centru arbore: ";
	if((lungime+1)%2==0)
	g<<coada[((lungime+1)/2)]<<" "<<coada[((lungime+1)/2)+1];
	else g<<visited[(lungime+1)/2];*/

	return 0;
}