Cod sursa(job #1094263)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 29 ianuarie 2014 09:22:28
Problema Diametrul unui arbore Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
const int NMAX = 100003;
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

int n,grad[NMAX],top,stiva[NMAX],d1,d2,i,x,y,rad,nodmax,tata[NMAX],ok,nodn;
vector <int> v[NMAX];

void parcurgere(int nod)
{
    int i;
    top++;
    //g<<top<<" ";
    stiva[top]=nod;
    if (top>d2)
    {
        d2=top;
    }
    if (grad[nod]!=0 && ok==0)
    {
        nodn=nod;
        parcurgere(tata[nod]);
    }
    else
    {
        ok=1;
    }
    if (ok==1)
    for (i=0;i<v[nod].size();i++)
    {
        if (v[nod][i]!=nodn)
            parcurgere(v[nod][i]);
    }
    top--;
}

void parcurgere1(int nod)
{
    int i;
    top++;
    stiva[top]=nod;
    if (v[nod].size()==0)
    {
        if (top>d1)
        {
            d1=top;
            nodmax=nod;
        }
    }
    for (i=0;i<v[nod].size();i++)
        parcurgere1(v[nod][i]);
    top--;
}

int main()
{
    f>>n;
    for (i=1;i<=n-1;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        grad[y]++;
        tata[y]=x;
    }
    for (i=1;i<=n;i++)
    {
        if (grad[i]==0)
        {
            rad=i;
            break;
        }
    }
    top=0;
    parcurgere1(rad);
    top=0;
    ok=0;
    parcurgere(nodmax);
    g<<d2;
    f.close();
    g.close();
    return 0;
}