Cod sursa(job #1706687)

Utilizator tiberiu1995Arsene Constantin-Tiberiu tiberiu1995 Data 22 mai 2016 23:40:53
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
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);

	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);
	}
	cost.resize(0);
	cost.resize(n, -1);

	first_try = bfs(0);
	//cout << first_try;

	cost.resize(0);
	cost.resize(n, -1);
	second_try = bfs(first_try);
	cout << second_try;
	cost.resize(0);
	cost.resize(n, -1);
	g << "Dimensiune diametru: " << dm;


	return 0;
}