Cod sursa(job #1261109)

Utilizator gerd13David Gergely gerd13 Data 11 noiembrie 2014 22:48:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>


using namespace std ;

const int NMAX = 100005 ;

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


vector <int> Graph[NMAX] ;
queue <int> Q ;
int N, cnt[NMAX], viz[NMAX], last, diam ;


void BFS(int k)
{
    memset(cnt, 0, sizeof(cnt)) ;
    memset(viz, 0, sizeof(cnt)) ;

    Q.push(k) ;

    cnt[k] = 1 ;
    viz[k] = 1 ;

    while(!Q.empty())
    {
        int act = Q.front() ;
        Q.pop() ;

        for(int i = 0 ; i < Graph[act].size() ; ++ i)
            if(viz[Graph[act][i]] == 0)
                {
                    Q.push(Graph[act][i]) ;
                    cnt[Graph[act][i]] = cnt[act] + 1 ;

                    viz[Graph[act][i]] = 1 ;

                    diam = cnt[Graph[act][i]] ;
                    last = Graph[act][i] ;
                }
    }
}

int main()
{

    fin >> N ;

    for(int i = 1 ; i <= N ; ++ i)
    {
        int X, Y ;
        fin >> X >> Y ;

        Graph[X].push_back(Y) ;
        Graph[Y].push_back(X) ;
    }

    BFS(1) ;
    BFS(last) ;

    fout << diam << '\n' ;

    fin.close() ;
    fout.close() ;
    return  0 ;
}