Cod sursa(job #1775921)

Utilizator raduzxstefanescu radu raduzx Data 10 octombrie 2016 20:04:10
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
struct nod
{
    int val;
    nod *urm;
};
typedef nod *pnod;
pnod v[100003];
int n;
void ad(int x,int y)
{
    pnod p=new nod;
    p->urm=v[x]->urm;
    p->val=y;
    v[x]->urm=p;
}
int t[100002];
bool viz[100002];
int latime(int varf)
{
    viz[varf]=1;
    t[1]=varf;
    pnod p;
    int k=1,s=1;
    while(k<=s)
    {
        p=v[t[k]]->urm;
        while(p)
        {
            if(viz[p->val]==0)
            {
                viz[p->val]=1;
                s+=1;
                t[s]=p->val;
            }
            p=p->urm;
        }
        k+=1;
    }
    return t[s];
}

int maxim;
int l;
void bfs(int varf,int l)
{
    pnod p=v[varf]->urm;
    l+=1;
     if(maxim<l)
                maxim=l;
    while(p)
    {
        if(viz[p->val]==1)
        {

            viz[p->val]=0;
            bfs(p->val,l);
            viz[p->val]=1;
        }
        p=p->urm;
    }
}
int main()
{
    int i,x,y;
    f>>n;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
    }
    for(i=1;i<n;i++)
    {
        f>>x>>y;
        ad(x,y);
        ad(y,x);
    }
    int o;
    o=latime(1);
    viz[o]=0;
    bfs(o,0);
    g<<maxim<<" ";
    return 0;
}