Cod sursa(job #1699135)

Utilizator vlad.dumitracheDumitrache Vlad vlad.dumitrache Data 6 mai 2016 11:10:56
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

int n, dm;
vector<vector<int>> graph;
vector<int> cost;

int bfs(int vertex)
{
	if (vertex < 0 || vertex > n - 1)
		return -1;
	queue <int> q;
	int element, i;
	q.push(vertex);
	cost[vertex] = true;
	while (!q.empty())
	{
		element = q.front();
		for (i = 0; i < graph[element].size(); i++)
		{
			if (cost[graph[element][i]] == -1)
			{
				q.push(graph[element][i]);
				cost[graph[element][i]] = cost[element] + 1;
			}
		}
		q.pop();
	}
	dm = cost[element];
	return element;
}

int main()
{
	f >> n;
	graph.resize(n);
	cost.resize(n, -1);
	int x, i, y, first_try, second_try;
	for (i = 0; i < n - 1; i++)
	{
		f >> x >> y;
		x--;
		y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	first_try = bfs(0);
	cost.resize(0);
	cost.resize(n, -1);
	second_try = bfs(first_try);
	g << dm;
	return 0;
}