Cod sursa(job #1344042)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 16 februarie 2015 11:41:57
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
#define Nmax 100001

vector< int > G[Nmax];
vector< bool > viz(Nmax);
int Q[Nmax], hmax, h;

void DFS(int) ;

int main()
{
    int i, n, a, b, st, dr, vf;
    vector< int >::iterator it;
    
    fin >> n;
    for(i = 1; i < n; ++i)
    {
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    Q[0] = 1; viz[1] = 1;
    for(st = dr = 0; st <= dr; ++st)
    {
        vf = Q[st];
        for(it = G[vf].begin(); it != G[vf].end(); ++it)
            if(!viz[*it])
            {
                Q[++dr] = *it;
                viz[*it] = 1;
            }
    }
    
    fill(viz.begin(), viz.end(), 0);
    h = 1;
    DFS( Q[n-1] );
    
    fout << hmax << '\n';
    
    return 0;
}

void DFS(int vf)
{
    vector< int >::iterator it;
    viz[vf] = 1;
    
    if(h > hmax) hmax = h;
    
    for(it = G[vf].begin(); it != G[vf].end(); ++it)
        if(!viz[*it])
    {
        ++h;
        DFS(*it);
        --h;
    }
}