Cod sursa(job #1654471)

Utilizator andreioneaAndrei Onea andreionea Data 17 martie 2016 04:45:34
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <unordered_map>
#include <queue>
#include <fstream>
#include <vector>
#include <algorithm>

using Edge = std::pair<int, int>;
using EdgeMap = std::unordered_multimap<int, int>;
class Tree
{
public:
	Tree(int N) : N(N) {}
	void Insert(Edge edge)
	{
		edges.insert({edge.first, edge.second});
		edges.insert({edge.second, edge.first});
	}
	Edge FarthestViaBFS(int startNode)
	{
		auto currNode = startNode;
		std::vector<int> diameter(N, 0);
		std::queue<int> q;
		diameter[startNode] = 1;
		while (true)
		{
			auto range = edges.equal_range(currNode);
			std::for_each(range.first, range.second,
				[&diameter, &q, currNode](EdgeMap::value_type& node)
				{
					if (!diameter[node.second])
					{
						q.push(node.second);
						diameter[node.second] = diameter[currNode] + 1;
					}
				});
			if (q.empty())
				return {currNode, diameter[currNode]};
			currNode = q.front();
			q.pop();
		}
	}
private:
	int N;
	EdgeMap edges;
};

int main()
{
	std::ifstream fin("darb.in");
	std::ofstream fout("darb.out");

	int N;
	fin >> N;

	Tree t(N);

	while (N--)
	{
		int a, b;
		fin >> a >> b;
		t.Insert({a, b});
	}

	int farthest_one;
	std::tie(farthest_one, std::ignore) = t.FarthestViaBFS(1);
	int result;
	std::tie(std::ignore, result) = t.FarthestViaBFS(farthest_one);

	fout << result;

	fin.close();
	fout.close();
}