Cod sursa(job #2219583)

Utilizator testsursaSurseTest testsursa Data 9 iulie 2018 13:30:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>

using namespace std;
int n,i,viz[100005],dist[100005],last;

struct gr
{
    int vecin;
    gr *urm;
}*cap[100005];

void add(gr *&head,int dest)
{
    if(head==NULL)
    {
        head=new gr;
        head->vecin=dest;
        head->urm=NULL;
    }
    else
    {
        gr *ad=new gr;
        ad->vecin=dest;
        ad->urm=head;
        head=ad;
    }
}

int dfs(int nod)
{
    gr *parc=cap[nod];

    viz[nod]=1;
    while(parc!=NULL)
    {
        if(viz[parc->vecin]==0)
       {
            dist[parc->vecin]=dist[nod]+1;
           dfs(parc->vecin);
       }
        parc=parc->urm;
    }
}

int main()
{
    ifstream cin("darb.in");
    ofstream cout("darb.out");
    cin>>n;
    for(i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        add(cap[a],b);
        add(cap[b],a);
    }
   dfs(1);
   int maxx=0;
   for(int i=1;i<=n;i++)
   {
    viz[i]=0;
    if(dist[i]>maxx)
    {
        maxx=dist[i];
        last=i;
    }
    dist[i]=0;
   }

   maxx=0;
    dfs(last);
    for(int i=1;i<=n;i++)
        if(dist[i]>maxx)
        {
            maxx=dist[i];
        }
    cout<<maxx+1;
    return 0;
}