Cod sursa(job #2169502)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 14 martie 2018 15:48:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define DMAX  100001

using namespace std;

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

struct elem{
    int val;
    elem *urm;
}*v[DMAX];

int n;//date de intrare
int nivel[DMAX], frunza, opusFrunza;

void citire(){
    in >> n;
    for(int i = 1; i <= n; i++){
        int a, b;
        in >> a >> b;

        elem *deAdaugat1 = new elem;
        deAdaugat1 -> val = b;
        deAdaugat1 -> urm = v[a];
        v[a] = deAdaugat1;

        elem *deAdaugat2 = new elem;
        deAdaugat2 -> val = a;
        deAdaugat2 -> urm = v[b];
        v[b] = deAdaugat2;

    }
}

void BF(int plec, int optiune){
    memset(nivel, -1, sizeof(nivel));
    int coada[DMAX], st, dr;
    coada[1] = plec;
    st = dr = 1;
    nivel[plec] = 0;

    while(st <= dr){
        int varf = coada[st];
        st++;
        elem * parcurg = v[varf];
        while(parcurg != NULL){
            if(nivel[parcurg -> val] == -1){
                coada[++dr] = parcurg -> val;
                nivel[parcurg -> val] = nivel[varf] + 1;
            }
            parcurg = parcurg -> urm;
        }
    }
    if(optiune == 0){
        frunza = coada[dr];
    }else{
        opusFrunza = coada[dr];
    }
}

void afisare(){
    out << nivel[opusFrunza] + 1;//adaugam 1 pentru ca frunza se afla pe nivelul 0
                                 //si nu intra la numaratoare
}

int main() {
    citire();
    BF(1, 0);// ma duc pe o frunza, caut o frunza
    BF(frunza, 1);//de la frunza ma duc la nodul cel mai indepartat si astfel diametrul
    afisare();
    return 0;
}