Cod sursa(job #2870044)

Utilizator the_horoHorodniceanu Andrei the_horo Data 12 martie 2022 00:38:50
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#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);
}