Cod sursa(job #2547316)

Utilizator alexilasiAlex Ilasi alexilasi Data 15 februarie 2020 11:16:50
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nMax = 100010;

int dmax, nd;
vector <int> v[nMax], prez;

void dfs(int nod, int dist)
{
    prez[nod] = true;
    for(auto it : v[nod])
        if(!prez[it])
            dfs(it, dist + 1);

    if(dist > dmax)
    {
        dmax = dist;
        nd = nod;
    }
}

int main()
{
    int n; fin >> n;
    prez.assign(n, 0);

    for(int i=0; i<n-1; i++)
    {
        int x, y; fin >> x >> y; x--; y--;
        v[x].push_back(y); v[y].push_back(x);
    }

    dfs(0, 0);

    prez.clear();
    prez.assign(n, 0);
    dmax = 0;

    dfs(nd, 0);

    fout << dmax + 1;
    return 0;
}