Cod sursa(job #2190239)

Utilizator Sergiu.VictorTalmacel Sergiu Victor Sergiu.Victor Data 30 martie 2018 11:18:10
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
#define N 1000001
int n,m;

struct node{
   int vf;
   node *next;}*lista[N];

void Addin(node *&prim, int x)
{
    node *p;
    p=new node;
    p->vf=x;
    p->next=prim;
    prim=p;
}

void Citire()
{
    for(int i=1;i<=n;i++)
          lista[i]=NULL;
    fin>>n;
    int a,b;
   for(int i=1;i<n;i++)
   {
       fin>>a>>b;

        Addin(lista[a],b);
        Addin(lista[b],a);
    }

}
int BFS(int x)
{
    int c[N],p,u,viz[N];
    p=u=1;
    c[u]=x;
    for(int i=1;i<=n;i++)
          viz[i]=-1;
    viz[x]=0;
    while(p<=u)
    {
        x=c[p++];
        for(node *i=lista[x];i;i=i->next)
             if(viz[i->vf]==-1)
        {
            c[++u]=i->vf;
            viz[i->vf]=viz[x]+1;
        }
    }
    int poz=0,maxi=-1;
    for(int i=1;i<=n;i++)
           if(viz[i]>maxi)
    {
        maxi=viz[i];
        poz=i;
    }

    return poz;
}
int main()
{
    Citire();
    int val=BFS(1);
    int r=BFS(val);
    fout<<r;

    return 0;
}