Cod sursa(job #2137441)

Utilizator mariakKapros Maria mariak Data 20 februarie 2018 19:55:32
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
FILE *fin  = freopen("darb.in", "r", stdin);
FILE *fout = freopen("darb.out", "w", stdout);

using namespace std;
/*-------Data-------*/
const int MAX = 1e5 + 2;
int n;
vector <int> G[MAX];
int max_lvl = -1, furthest, lvl[MAX];
/*------------------*/

void Read(){
    scanf("%d", &n);
    for(int i = 1; i < n; ++ i){
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

void Dfs(int node, int dad){
    for(int son : G[node])
        if(son != dad){
            lvl[son] = lvl[node] + 1;
            if(lvl[son] > max_lvl){
                max_lvl = lvl[son];
                furthest = son;
            }
            Dfs(son, node);
        }
}

int main(){
    Read();
    lvl[1] = 0; Dfs(1, 0);
    max_lvl = -1;
    lvl[furthest] = 0; Dfs(furthest, 0);
    printf("%d\n", lvl[furthest] + 1);
    return 0;
}