Mai intai trebuie sa te autentifici.

Cod sursa(job #1691191)

Utilizator Bijoux12Andreea Gae Bijoux12 Data 17 aprilie 2016 11:02:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int bfs(int vertex)
{
	queue <int> q;
	int element, i;
	q.push(vertex);
	visited[vertex] = true;
	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();
	}
	dim=visited[element];
	return element;

}

int main()
{
	int i,x,y;
	f >> n;
	graph.resize(n);
	visited.resize(n, -1);
	for (i = 0; i < n - 1; i++)
	{
		f >> x >> y;
		x--;
		y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	x = bfs(0);
	visited.clear();
	visited.resize(n, -1);
	y = bfs(x);
	g<<dim;
	return 0;
}