Cod sursa(job #2817574)

Utilizator schizofrenieShallan Davar schizofrenie Data 13 decembrie 2021 21:18:29
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#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);
}