Cod sursa(job #1123918)

Utilizator RadEmanuelRad Emanuel RadEmanuel Data 26 februarie 2014 10:40:47
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<fstream>
#include<list>
#include<vector>
#define dmax 100000
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
list<int> lista;
list<int>::iterator it;
vector< list<int> >l(dmax,lista);
int x,y,n,lmax,lu,primul,viz[dmax],i;

void df(int nod)
{
    list<int>::iterator it;
    for(it=l[nod].begin();it!=l[nod].end();++it)
        if(!viz[*it])
        {
            viz[*it]=1;
            ++lu;
            if(lu>lmax)
                primul=*it,
                lmax=lu;
            df(*it);
            --lu;
            viz[*it]=0;
        }
}

int main()
{
    fin>>n;
    for(i=1;i<n;++i)
    {
        fin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    viz[1]=1;
    df(1);
    lu=0;
    for(i=1;i<=n;++i) viz[i]=0;
    df(primul);
    fout<<lmax+1;
    return 0;
}