Cod sursa(job #2414272)

Utilizator capmareAlexCapmare Alex capmareAlex Data 24 aprilie 2019 13:51:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n;
vector< int > v[NMAX];
int sol;
int fr[NMAX], D[NMAX],ultim;
void bfs(int k)
{
    for(int i = 1; i <= n; ++i)fr[i] = 0, D[i] = 0;
    fr[k] = 1;
    D[k] = 1;
    queue< int > q;
    q.push(k);
    while( q.size() )
    {
        int x = q.front();
        q.pop();
        for(int i=0; i< v[x].size(); ++i)
            if( !fr[v[x][i]])
        {
            fr[v[x][i]] = 1;
            D[v[x][i]] = D[x]+1;
            q.push(v[x][i]);
            ultim=v[x][i];
        }
    }
}
int main()
{
    fin >> n;
    for(int i = 1; i < n ; ++i)
    {
        int x, y;
        fin >> x >> y;
        v[x].push_back( y );
        v[y].push_back( x );
    }
    bfs(1);
    int frunza=ultim;
    bfs(frunza);
    fout<<D[ultim];
    return 0;
}