Cod sursa(job #1658667)

Utilizator bragaRObragaRO bragaRO Data 21 martie 2016 18:40:16
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

int m, n;
vector <vector <int> > graph;
vector <int> visited;
ifstream f("darb.in");
ofstream h("darb.out");

int poz1, poz2;

void bfs(int vertex)
{
	if (vertex<0 || vertex>n - 1) return;

	queue <int> q;
	int element;
	unsigned int i;

	q.push(vertex);

	for(i=0;i<(unsigned int)n;i++) visited[i]=-1;
	visited[vertex] = 0;

	while (!q.empty())
	{
		element = q.front();
		for (i = 0; i < graph[element].size(); i++)
			if (visited[graph[element][i]]==-1)
			{
				q.push(graph[element][i]);
				visited[graph[element][i]] = visited[element]+1;
			}
		q.pop();
	}

}


int main()
{
	int x, y, i,nod;
	f >> n;
	m=n-1;
	nod=n;
    nod--;
	graph.resize(n);
	visited.resize(n, false);

	for (i = 0; i<m; i++)
	{
		f >> x >> y;
		x--; y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	bfs(nod);

	poz1=0; poz2=0;
	for(i=1;i<n;i++)
        if(visited[i]>visited[poz1]) poz1=i;

    bfs(poz1);

    for(i=0;i<n;i++)
        if(visited[i]>visited[poz2]) poz2=i;

    h << visited[poz2]+1;

	f.close();
	h.close();
	return 0;
}