Cod sursa(job #2121712)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 4 februarie 2018 11:24:56
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>

using namespace std;

int n;
vector<int> vecini[100005];
int depth[100005];

void citire(){
    scanf("%d", &n);

    int a, b;

    for(int i = 1; i < n; i++){
        scanf("%d %d", &a, &b);

        a--;
        b--;

        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }
}

void dfs(int x){
    int l = vecini[x].size();

    for(int i = 0; i < l; i++){
        if(depth[vecini[x][i]] == 0){
            depth[vecini[x][i]] = depth[x] + 1;
            dfs(vecini[x][i]);
        }
    }
}

void solve(){
    depth[0] = 1;
    dfs(0);

    int valMax = 0, pos;

    for(int i = 0; i < n; i++){
        if(depth[i] > valMax){
            valMax = depth[i];
            pos = i;
        }

        depth[i] = 0;
    }

    depth[pos] = 1;
    dfs(pos);

    valMax = 0;

    for(int i = 0; i < n; i++){
        if(depth[i] > valMax){
            valMax = depth[i];
        }
    }

    printf("%d", valMax);
}

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    citire();
    solve();

    return 0;
}