Cod sursa(job #1654469)

Utilizator andreioneaAndrei Onea andreionea Data 17 martie 2016 04:31:30
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <unordered_map>
#include <queue>
#include <fstream>
#include <vector>
#include <algorithm>
class Tree
{
public:
	Tree(uint32_t N) : N(N) {}
	void Insert(std::pair<uint32_t, uint32_t> edge)
	{
		edges.insert({edge.first, edge.second});
		edges.insert({edge.second, edge.first});
	}
	std::pair<uint32_t, uint32_t> FarthestViaBFS(uint32_t startNode)
	{
		auto currNode = startNode;
		std::vector<uint32_t> diameter(N, 0);
		std::queue<uint32_t> q;
		diameter[startNode] = 1;
		while (true)
		{
			auto range = edges.equal_range(currNode);
			std::for_each(range.first, range.second,
				[&diameter, &q, currNode](std::unordered_multimap<uint32_t, uint32_t>::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:
	uint32_t N;
	std::unordered_multimap<uint32_t, uint32_t> edges;
};

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

	uint32_t N;
	fin >> N;

	Tree t(N);

	uint32_t a, b;

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

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

	fout << result << "\n";

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