Cod sursa(job #2796874)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 8 noiembrie 2021 22:01:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
/*
Diametrul unui arbore
Diametrul unui arbore reprezintă lungimea drumului (ca numar de noduri) intre cele mai departate două frunze.

Cerinţă
Dându-se un arbore cu N noduri, să se determine diametrul acestuia.

Date de intrare
Pe prima linie a fisierului darb.in se afla N cu specificatiile de mai sus. Pe următoarele N-1 linii se află cate o pereche de numere a si b reprezentând muchiile arborelui.

Date de ieşire
În fişierul de ieşire darb.out se va afisa diametrul arborelui.

Restricţii
2 ≤ N ≤ 100.000
*/
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define NMAX 100005

using namespace std;

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

vector < int > v[NMAX];
int nrmax, j;

void dfs1(int x, int prec, int nr);
void dfs2(int x, int prec, int nr);

int main()
{
    int n, x, y;

    fin >> n;
    while(n--)
    {
        fin >> x >> y;
        v[x].pb(y), v[y].pb(x);
    }

    dfs1(1, 0, 1);
    dfs2(j, 0, 1);

    fout << nrmax;

    return 0;
}

void dfs1(int x, int prec, int nr)
{
    if(nr > nrmax) nrmax = nr, j = x;
    for(auto it:v[x]) if(it != prec) dfs1(it, x, nr + 1);
}

void dfs2(int x, int prec, int nr)
{
    if(nr > nrmax) nrmax = nr;
    for(auto it:v[x]) if(it != prec) dfs2(it, x, nr + 1);
}

/*
IN:
11
1 2
1 3
1 4
2 5
3 6
4 7
5 8
5 9
6 10
10 11

OUT:
8
*/