Cod sursa(job #1996718)

Utilizator GinguIonutGinguIonut GinguIonut Data 2 iulie 2017 14:28:12
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>

#define nMax 100001

using namespace std;

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

int n, nodeSol, distMax;

struct lista
{
    int val;
    lista *nxt;
};

lista *head[nMax]={NULL};

void depthFirstSearch(int node, int tata, int dist)
{
    if(dist>distMax)
    {
        distMax=dist;
        nodeSol=node;
    }

    lista *nod=head[node];
    while(nod!=NULL)
    {
        int fiu=nod->val;
        if(fiu==tata)
            continue;
        depthFirstSearch(fiu, node, dist+1);
        nod=nod->nxt;
    }
}

void insertFront(lista * &hd, int v)
{
    lista *elem=new lista;
    elem->val=v;
    elem->nxt=hd;
    hd=elem;
}

int main()
{
    int a, b;
    fin>>n;
    for(int i=1; i<n; i++)
    {
        fin>>a>>b;
        insertFront(head[a], b);
        insertFront(head[b], a);
    }

    depthFirstSearch(1, 0, 0);
    depthFirstSearch(nodeSol, 0, 0);
    fout<<distMax;
}