Cod sursa(job #2863735)

Utilizator the_horoHorodniceanu Andrei the_horo Data 7 martie 2022 09:43:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <array>
#include <fstream>
#include <vector>
#include <queue>


enum class BfsTarget {
    deepestNode, biggestDepth
};


constexpr size_t MAX_NODES = 100000;


size_t nodes;

std::array<std::vector<size_t>, MAX_NODES> edges;


template<BfsTarget bfsTarget>
size_t bfs (size_t start) {
    std::queue<size_t> q({start});
    std::vector<size_t> depth(nodes);

    depth[start] = 1;

    size_t nowNode = start;
    while (!q.empty()) {
        nowNode = q.front();
        q.pop();

        for (auto to: edges[nowNode]) {
            if (depth[to] == 0) {
                depth[to] = depth[nowNode] + 1;
                q.emplace(to);
            }
        }
    }

    if constexpr (bfsTarget == BfsTarget::deepestNode) {
        return nowNode;
    } else if (bfsTarget == BfsTarget::biggestDepth) {
        return depth[nowNode];
    }
}

void readInput () {
    std::ifstream file("darb.in");
    file.exceptions(file.badbit | file.eofbit | file.failbit);
    file >> nodes;

    for (size_t i = 0; i != nodes - 1; ++ i) {
        size_t x, y;
        file >> x >> y;
        -- x, -- y;

        edges[x].emplace_back(y);
        edges[y].emplace_back(x);
    }
}


void writeAnswer (size_t diameter) {
    std::ofstream file("darb.out");
    file.exceptions(file.badbit | file.eofbit | file.failbit);

    file << diameter;
}

int main () {
    readInput();

    const size_t deepestNode = bfs<BfsTarget::deepestNode>(0);
    const size_t depth = bfs<BfsTarget::biggestDepth>(deepestNode);

    writeAnswer(depth);
}