Cod sursa(job #2503141)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 2 decembrie 2019 16:19:11
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f ("darb.in") ;
ofstream g ("darb.out") ;
int N , x ,y ;
vector <int> v[NMAX];
bool viz[NMAX];
int lg[NMAX] , sol = 0 , frunza;
queue <int> q;
// doua bf-uri primul pentru a gasi cea mai adanca frunza,  iar cel de-al doilea pentru a gasi solutia = lg maxima in arbore(diametrul sau)
void BFS (int nod)
{
      lg[nod] = 1;
    viz[nod] = true;
    q.push(nod);
    while (!q.empty())
    {
        nod = q.front();
          q.pop();
        int len = v[nod].size();
        for (int i = 0 ; i < len  ;++i)
        {
            int vec = v[nod][i];
            if (!viz[vec])
            {

                viz[vec] = true;
                lg[vec] = lg[nod] + 1;
                if (lg[vec] > sol) {sol = lg[vec] , frunza = vec;}
                q.push(vec);
            }
        }

    }
}
int main()
{
    f >> N ;
    for (int i = 1 ; i <= N - 1 ; ++i)
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    BFS(1);

    for (int i = 1 ; i <= N ; ++i)
        {
        viz[i] = false;
        lg[i] = 0 ;
        }
        sol = 0 ;
    BFS(frunza);

    g << sol << '\n';
    f.close();
    g.close();
    return 0;
}