Pagini recente » Cod sursa (job #514967) | Cod sursa (job #2750178) | Cod sursa (job #2073) | Cod sursa (job #2085943) | Cod sursa (job #2870044)
#include <fstream>
#include <vector>
#include <queue>
using graphT = std::vector<std::vector<size_t>>;
struct BfsResult {
size_t deepestNode;
size_t depth;
};
BfsResult bfs (const graphT &edges, size_t start) {
std::vector<size_t> depth(edges.size());
std::queue<size_t> q;
depth[start] = 1;
q.emplace(start);
size_t node;
while (!q.empty()) {
node = q.front();
q.pop();
for (auto to: edges[node])
if (depth[to] == 0) {
depth[to] = depth[node] + 1;
q.emplace(to);
}
}
return { node, depth[node] - 1 };
}
size_t diameter (const graphT &edges) {
const auto deepestNode = bfs(edges, 0).deepestNode;
const auto diameter = bfs(edges, deepestNode).depth + 1;
return diameter;
}
int main () {
std::ifstream in("darb.in");
std::ofstream out("darb.out");
size_t nodeCount;
in >> nodeCount;
graphT edges(nodeCount);
for (size_t i = 0; i != nodeCount - 1; ++ i) {
size_t u, v;
in >> u >> v;
-- u, -- v;
edges[u].emplace_back(v);
edges[v].emplace_back(u);
}
out << diameter(edges);
}