Cod sursa(job #2404432)

Utilizator EmanuelIMIacob Emanuel EmanuelIM Data 12 aprilie 2019 19:13:18
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

struct nod
{
    int info;
    nod *urm;
}*prim[100005];

int n,viz[100005],C[100005];

void adin(nod *&prim,int x)
{
    nod *nou=new nod;
    nou->info=x;
    nou->urm=prim;
    prim=nou;
}

void citire()
{
    fin>>n;
    int x,y;
    while(fin>>x>>y)
    {
        adin(prim[x],y);
        adin(prim[y],x);
    }
}

void BFS(int x,int &maxi)
{
    int P,u,i;
    P=u=1;
    C[P]=x;
    viz[x]=1;
    nod *q;
    maxi=0;viz[maxi]=0;
    while(P<=u)
    {
        x=C[P++];
        for(q=prim[x];q;q=q->urm)
            if(viz[q->info]==0)
        {
            C[++u]=q->info;
            viz[q->info]=viz[x]+1;
            if(viz[q->info]>viz[maxi]) maxi=q->info;
        }
    }
}

int main()
{
    int maxi;
    citire();
    BFS(1,maxi);
    int x=maxi;
    for(int i=1;i<=n;i++) viz[i]=0;
    BFS(x,maxi);
    maxi=-1;
    for(int i=1;i<=n;i++) if(viz[i]>maxi) maxi=viz[i];
    fout<<maxi;
    return 0;
}