Cod sursa(job #2555748)

Utilizator copanelTudor Roman copanel Data 24 februarie 2020 12:07:14
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>

std::vector<int> muchii[100000];
int max_depth, max_depth_node;

void dfs(int nod, int depth, int parent) {
    if (depth > max_depth) {
        max_depth_node = nod;
        max_depth = depth;
    }
    for (const int fiu : muchii[nod]) {
        if (fiu != parent) {
            dfs(fiu, depth + 1, nod);
        }
    }
}

int main()
{
    std::ifstream fin("darb.in");
    std::ofstream fout("darb.out");
    int n;

    fin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        fin >> a >> b;
        a--; b--;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }

    max_depth = max_depth_node = 0;
    dfs(0, 1, 0);
    int farthest = max_depth_node;
    max_depth = max_depth_node = 0;
    dfs(farthest, 1, farthest);

    fout << max_depth;
    return 0;
}