Pagini recente » Cod sursa (job #1939880) | Cod sursa (job #1221785) | Cod sursa (job #179134) | Cod sursa (job #741) | Cod sursa (job #1654472)
#include <unordered_map>
#include <queue>
#include <fstream>
#include <vector>
#include <algorithm>
using Edge = std::pair<int, int>;
using Result = 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});
}
Result 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](auto& 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();
}