Cod sursa(job #3198439)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 29 ianuarie 2024 12:18:36
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
//  Tree Diameter - CSES

#include <iostream>
#include <vector>

struct Graph {
private:
    std::vector<std::vector<int>> adj;
    std::vector<int> depth;
    int size;

    void dfs_depth(int node, int root = 0) {
        depth[node] = 1 + depth[root];

        for (const auto &x: adj[node]) {
            if (x == root) continue;
            dfs_depth(x, node);
        }
    }

public:
    explicit Graph(int size) : size(size) {
        adj.resize(size + 1);
        depth.resize(size + 1);
    }

    void add_edge(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    int get_diameter() {
        depth[0] = -1;
        dfs_depth(1);
        int next = 1;
        for (int i = 2; i <= size; ++i) {
            if (depth[i] > depth[next]) next = i;
        }

        dfs_depth(next);
        int max = 0;
        for (int i = 1; i <= size; ++i) max = std::max(max, depth[i]);
        return max;
    }

};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int n;
    std::cin >> n;
    Graph tree(n);

    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        std::cin >> a >> b;
        tree.add_edge(a, b);
    }

    std::cout << tree.get_diameter();
    return 0;
}