Pagini recente » Cod sursa (job #1594146) | Cod sursa (job #2066951) | Cod sursa (job #1034460) | Cod sursa (job #591817) | Cod sursa (job #1655434)
#include <unordered_map>
#include <queue>
#include <fstream>
#include <vector>
#include <algorithm>
using Edge = std::pair<uint32_t, uint32_t>;
using Result = std::pair<uint32_t, uint32_t>;
using EdgeMap = std::unordered_multimap<uint32_t, uint32_t>;
class Tree
{
public:
Tree(uint32_t N) : N(N) {}
void Insert(Edge edge)
{
edges.insert({edge.first, edge.second});
edges.insert({edge.second, edge.first});
}
Result 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](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:
uint32_t N;
EdgeMap edges;
};
int main()
{
std::ifstream fin("darb.in");
std::ofstream fout("darb.out");
uint32_t N;
fin >> N;
Tree t(N);
while (N--)
{
uint32_t a, b;
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;
fin.close();
fout.close();
}