Diametrul unui arbore in C++

Diametrul unui arbore reprezintă lungimea drumului (ca numar de noduri) intre cele mai departate două frunze.

Problema darb – infoarena.ro

In continuare, pentru implementarea algoritmului vom rezolva problema darb de pe infoarena.ro.

Cerinta:

Dandu-se un arbore cu N noduri, sa se determine diametrul acestuia.

Avand urmatorul graf:

Diagrama diametrul unui arbore

Noi trebuie sa aflam distanta cea mai indepartata intre doua noduri. Aceasta distanta este 5 in cazul nostru (drumul 5 – 1 – 2 – 3 – 4). Dar cum putem ajune la acest rezultat?

O prima varianta este sa parcurgem in inaltime fiecare nod in parte si sa retinem cea mai mare distanta rezultata din toate parcurgerile. Aceasta solutie nu este optima din pacate, avand o complexitate de O(N²).

Prima solutie (40 puncte) – Complexitate O(N²)

#include    <cstdio>
#include    <vector>
#include    <fstream>

using namespace std;

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

#define MAX_N 100000

int N;

vector< int > V[MAX_N];
bool vizitat[MAX_N];
int raspuns;

void Read()
{
    fin >> N;
    for(int i = 1; i < N; i++)
    {
        int x, y;
        fin >> x >> y;
        --x, --y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
}

void DFS(int Nod, int Distanta)
{
    if(Distanta > raspuns)
        raspuns = Distanta;

    vizitat[Nod] = true;
    for(unsigned int i = 0; i < V[Nod].size(); i++)
    {
        if(!vizitat[V[Nod][i]])
            DFS(V[Nod][i], Distanta + 1);
    }

    vizitat[Nod] = false;
}


int main()
{
    Read();

    for(int i = 0; i < N; i++)
        DFS(i, 0);

    fout << raspuns + 1;
}

Diametrul unui arbore

A doua solutie insa se bazeaza doar pe doua parcurgeri in latime sau adancime. Pornim prima parcurgere dintr-un nod aleatoriu si ne vom oprii intr-un nod ce reprezinta cea mai indepartata frunza din prima parcurgere. Cel de-a doua parcurgere v-a pornii din acest nod si va determina a doua cea mai indepartata frunza.

A doua solutie (problema darb – infoarena.ro)

#include    <iostream>
#include    <fstream>
#include    <vector>

using namespace std;

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

const int NLIM = 100005;

int N;
int nivelMaxim, pozitieNivel;
vector  < int > Muchii[NLIM];

bool vizitat[NLIM];

void DFS(int Nod, int nivel)
{
    vizitat[Nod] = true;
    if(nivel > nivelMaxim)
    {
        nivelMaxim = nivel;
        pozitieNivel = Nod;
    }
    for(unsigned int i = 0; i < Muchii[Nod].size(); i++)
    {
        int Vecin = Muchii[Nod][i];
        if(!vizitat[Vecin])
            DFS(Vecin, nivel + 1);
    }
}

void Reset()
{
    for(int i = 1; i <= N; i++)
        vizitat[i] = false;
}

void Read()
{
    int x, y;
    fin >> N;
    for(int i = 1; i < N; i++)
    {
        fin >> x >> y;
        Muchii[x].push_back(y);
        Muchii[y].push_back(x);
    }
    DFS(1,0);

    Reset();

    DFS(pozitieNivel, 0);
    fout << nivelMaxim + 1;
}

int main() {
    Read();
    return 0;
}