Pagini recente » Cod sursa (job #486408) | Cod sursa (job #1183285) | Cod sursa (job #93965) | Cod sursa (job #1980246) | Cod sursa (job #1655444)
#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, uint64_t>;
using EdgeMap = std::unordered_multimap<uint64_t, uint64_t>;
class Tree
{
public:
Tree(uint64_t N) {q.resize(N); diameter.resize(N);}
void Insert(Edge edge)
{
edges.insert({edge.first, edge.second});
edges.insert({edge.second, edge.first});
}
Result FarthestViaBFS(uint64_t startNode)
{
std::fill(diameter.begin(), diameter.end(), 0ull);
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++];
}
}
private:
EdgeMap edges;
std::vector<uint32_t> q;
std::vector<uint64_t> diameter;
};
int main()
{
std::ifstream fin("darb.in");
std::ofstream fout("darb.out");
uint64_t N;
fin >> N;
Tree t(N);
while (N--)
{
uint64_t a, b;
fin >> a >> b;
t.Insert({a, b});
}
uint32_t farthest_one;
std::tie(farthest_one, std::ignore) = t.FarthestViaBFS(1);
uint64_t result;
std::tie(std::ignore, result) = t.FarthestViaBFS(farthest_one);
fout << result;
fin.close();
fout.close();
}