Cod sursa(job #1655449)

Utilizator andreioneaAndrei Onea andreionea Data 17 martie 2016 23:36:05
Problema Diametrul unui arbore Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 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(int64_t 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(int64_t startNode)
	{
		auto currNode = startNode;
		diameter[startNode] = 1;
		size_t idx = 0;
		size_t endx = 0;
		while (true)
		{
			auto range = edges.equal_range(currNode);
			std::for_each(range.first, range.second,
				[this, &endx, currNode](EdgeMap::value_type& node)
				{
					if (!diameter[node.second])
					{
						q[endx++] = (node.second);
						diameter[node.second] = diameter[currNode] + 1;
					}
				});
			if (endx == idx)
				return {currNode, diameter[currNode]};
			currNode = q[idx++];
		}
	}
	Result FarthestViaBFS2(int64_t startNode)
	{
		auto currNode = startNode;
		diameter[startNode] = -1;
		size_t idx = 0;
		size_t endx = 0;
		while (true)
		{
			auto range = edges.equal_range(currNode);
			std::for_each(range.first, range.second,
				[this, &endx, currNode](EdgeMap::value_type& node)
				{
					if (diameter[node.second] > 0)
					{
						q[endx++] = (node.second);
						diameter[node.second] = diameter[currNode] - 1;
					}
				});
			if (endx == idx)
				return {currNode, -diameter[currNode]};
			currNode = q[idx++];
		}
	}
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();
}