Cod sursa(job #2963005)

Utilizator rastervcrastervc rastervc Data 9 ianuarie 2023 23:39:25
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <queue>

std::ifstream fin("darb.in");
std::ofstream fout("darb.out");

constexpr std::size_t LIM = 1e5 + 1;

static inline std::pair<int, int> furthest(
    std::size_t node_cnt,
    std::vector<int> (&adj_list)[LIM],
    int node 
) noexcept {
    std::vector<int> distance(node_cnt + 1, -1);
    distance[node] = 0;
    std::queue<int> queue;
    queue.push(node);

    int last_node = 0;
    while (!queue.empty()) {
        node = queue.front();
        queue.pop();
        for (const int adj_node : adj_list[node])
            if (distance[adj_node] == -1) {
                distance[adj_node] = distance[node] + 1;
                last_node = adj_node;
                queue.push(adj_node);
            }
    }

    return { last_node, distance[last_node] };
}

int main() {
    std::vector<int> adj_list[LIM];
    int N, node1, node2;

    fin >> N;
    while (fin >> node1 >> node2) {
        adj_list[node1].push_back(node2);
        adj_list[node2].push_back(node1);
    }

    auto[ext1, temp] = furthest(N, adj_list, 1);
    auto[ext2, dist] = furthest(N, adj_list, ext1);
    
    fout << dist + 1;

    fin.close();
    fout.close();
    return 0;
}