Cod sursa(job #1655459)

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

using Edge = std::pair<int, int>;
using Result = std::pair<int, int64_t>;
using EdgeMap = std::unordered_multimap<int64_t, int64_t>;

class Tree
{
public:
	Tree(int N) : diameter(N, 0) {q.resize(N);}
	void Insert(Edge edge)
	{
		edges.insert({edge.first, edge.second});
		edges.insert({edge.second, edge.first});
	}
	Result FarthestViaBFS1(int startNode)
	{
		auto currNode = startNode;
		diameter[startNode] = 1;
		auto topQ = q.begin();
		auto endQ = q.begin();
		while (true)
		{
			auto range = edges.equal_range(currNode);
			std::for_each(range.first, range.second,
				[this, &endQ, &currNode](EdgeMap::value_type& node)
				{
					if (diameter[node.second] == 0)
					{
						*(endQ++) = (node.second);
						diameter[node.second] = diameter[currNode] + 1;
					}
				});
			if (q.end() == topQ)
				return {currNode, diameter[currNode]};
			currNode = *(topQ++);
		}
	}
	Result FarthestViaBFS2(int startNode)
	{
		auto currNode = startNode;
		diameter[startNode] = -1;
		auto topQ = q.begin();
		auto endQ = q.begin();
		while (true)
		{
			auto range = edges.equal_range(currNode);
			std::for_each(range.first, range.second,
				[this, &endQ, &currNode](EdgeMap::value_type& node)
				{
					if (diameter[node.second] > 0)
					{
						*(endQ++) = (node.second);
						diameter[node.second] = diameter[currNode] - 1;
					}
				});
			if (q.end() == topQ)
				return {currNode, -diameter[currNode]};
			currNode = *(topQ++);
		}
	}
private:
	EdgeMap edges;
	std::vector<int> q;
	std::vector<int64_t> diameter;
};

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.FarthestViaBFS1(1);
	int64_t result;
	std::tie(std::ignore, result) = t.FarthestViaBFS2(farthest_one);

	fout << result;

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