Cod sursa(job #2107970)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 17 ianuarie 2018 20:25:14
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

int maxim , n ;
vector<int> graf[100001] ;
int dist[100001] ;
bool viz[100001] ;

int BFS(int nod)
{
    int ct ;
    maxim = 0 ;
    queue<int> Q;
    Q.push(nod) ;
    memset(dist,0,4*n+4) ;
    memset(viz,false,n+1) ;
    viz[nod] = true ;
    while(!Q.empty())
    {
        nod = Q.front();
        Q.pop() ;
        for ( int i = 0 ; i < graf[nod].size() ; i++ )
        {
            if ( viz[graf[nod][i]] == false )
            {
                viz[graf[nod][i]] = true ;
                dist[graf[nod][i]] = dist[nod]+1 ;
                Q.push(graf[nod][i]) ;
                if ( dist[graf[nod][i]] > maxim )
                {
                    maxim = dist[graf[nod][i]] ;
                    ct = graf[nod][i] ;
                }
            }
        }
    }
    return ct ;
}

int main()
{
    int x , y , i ;
    ifstream fin ("darb.in") ;
    ofstream fout("darb.out") ;
    fin >> n ;
    for ( i = 1 ; i < n ; i++ )
    {
        fin >> x >> y ;
        graf[x].push_back(y);
        graf[y].push_back(x) ;
    }
    x = BFS(1) ;
    y = BFS(x) ;
    fout << maxim+1 ;
}