Cod sursa(job #1464711)

Utilizator petru.cehanCehan Petru petru.cehan Data 24 iulie 2015 12:28:26
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>

#define NMax 100010

using namespace std;

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

int nodes, dist[NMax], leaf , Max = -1 ;
bool mark[NMax] ;
queue<int> Q ;
vector<int> G[NMax] ;

void BFS ( int node )
{
    Q.push(node) ;
    memset ( dist , 0 , sizeof( dist ) ) ;
    memset ( mark , false , sizeof ( mark ) ) ;

    mark[node] = true ;

    while ( !Q.empty() )
    {

        int crtNode = Q.front() ;
        Q.pop() ;

        for ( vector < int > :: iterator it = G[crtNode].begin() ; it != G[crtNode].end() ; ++ it )
        {
            if ( !mark[*it] )
            {
                Q.push(*it) ;
                mark[*it] = true ;

                dist[*it] = dist[crtNode] + 1 ;

                Max = dist[*it] ;
                leaf = *it ;
            }
        }

    }
}

int main()
{
    fin >> nodes;

    int n1 , n2 ;
    for ( int i = 1 ; i <= nodes ; ++ i )
    {
        fin >> n1 >> n2;

        G[n1].push_back(n2);
        G[n2].push_back(n1);
    }

    BFS(1) ; // Prima parcurgere
    BFS(leaf) ; // A doua parcurgere

    fout << Max + 1 ;

    return 0;
}