Pagini recente » Cod sursa (job #3205793) | Cod sursa (job #648484) | Cod sursa (job #1936948) | Cod sursa (job #179789) | Cod sursa (job #2817574)
#include <bits/stdc++.h>
constexpr size_t MAXN = 1e5;
int
bfs (int node, const std::vector<std::vector<int>> &edges) {
static int depth[2][MAXN];
static bool passNumber = 0;
std::queue<int> q;
depth[passNumber][node] = 1;
q.emplace(node);
while (!q.empty()) {
node = q.front();
q.pop();
for (auto to: edges[node])
if (depth[passNumber][to] == 0) {
depth[passNumber][to] = depth[passNumber][node] + 1;
q.emplace(to);
}
}
/* The first pass returns the deepest node, the second its depth */
if (passNumber == 0) {
passNumber = 1;
return node;
} else {
return depth[passNumber][node];
}
}
int main () {
int n;
std::ifstream f("darb.in");
std::ofstream g("darb.out");
std::vector<std::vector<int>> edges;
f >> n;
edges.resize(n);
for (int i = 1; i < n; ++ i) {
int de, la;
f >> de >> la;
-- de, -- la;
edges[de].emplace_back(la);
edges[la].emplace_back(de);
}
g << bfs(bfs(0, edges), edges);
}