Cod sursa(job #1363992)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 27 februarie 2015 13:25:50
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
using namespace std;
struct nod
{
    int x;
    nod *leg;
};
nod *p,*v[100002];
int viz[100002];
int q=1;
void dfs(int x)
{
    nod *p;
    viz[x]=q;
    for(p=v[x];p!=0;p=p->leg)
    {
        if(viz[p->x]==0)
        {
         q++;
         dfs(p->x);
         q--;
        }
    }
}
int n,i,x,y,w,vmax,e,poz;
int main()
{
     ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin>>n;
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
        v[i]=0;
    }
    for(i=1;i<n;i++)
    {
        fin>>x>>y;
        p=new nod;
        p->x=y;
        p->leg=v[x];
        v[x]=p;
        p=new nod;
        p->x=x;
        p->leg=v[y];
        v[y]=p;
    }
    dfs(1);
    e=viz[1];
    for(i=1;i<=n;i++)
    {
        if(viz[i]>e)
        {
            e=viz[i];
            poz=i;
        }
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
    }
    dfs(poz);
    vmax=viz[1];
    for(i=2;i<=n;i++)
    {
        if(viz[i]>vmax)
        {
            vmax=viz[i];
        }
    }
    fout<<vmax;
    fin.close();
    fout.close();
    return 0;
}