Cod sursa(job #1205736)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 7 iulie 2014 22:40:33
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <array>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
const int kMaxSize = 100000;
void read(int& tree_size, array<vector<int>, kMaxSize>& graph)
{
	ifstream fin("darb.in");
	fin >> tree_size;
	for (int i = 0; i < tree_size - 1; ++i)
	{
		int x = 0, y = 0;
		fin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	fin.close();
}
void write(const int& max_dist)
{
	ofstream fout("darb.out");
	fout << max_dist << '\n';
	fout.close();
}
//returns a pair. First is the node and second is the distance
pair<int, int> bfs(const int& tree_size, const int& start,
				const array<vector<int>, kMaxSize>& G)
{
	int max_dist = -1;
	array<bool, kMaxSize> seen;
	fill(seen.begin(), seen.end(), false);

	pair<int, int> farthest;
	queue<pair<int, int>> q;
	q.push(make_pair(start, 1));
	while (!q.empty())
	{
		pair<int, int> front = q.front();
		q.pop();

        int u = front.first, dist = front.second;
        if (dist > max_dist)
			farthest = front;
		for (const auto& v: G[u])
		{
			if (!seen[v])
			{
				seen[v] = true;
				q.push(make_pair(v, dist + 1));
			}
		}
	}
	return farthest;
}
int main()
{
	int tree_size = 0;
	array<vector<int>, kMaxSize> t;
	read(tree_size, t);

    int u = bfs(tree_size, 1, t).first;
    int max_dist = bfs(tree_size, u, t).second;
	write(max_dist);
	return 0;
}