Cod sursa(job #2428474)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 5 iunie 2019 15:16:37
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.01 kb
#include <vector>
#include <fstream>

// numarul maxim de noduri in arbore
#define MAX_N 100005

using namespace std;
// numarul de noduri in arbore si numarul de muchii

int n;
// graful memorat prin liste de adiacenta
vector<int> graf[MAX_N];

// daca un nod a fost deja parcurs
bool parcurs[MAX_N];
// distanta maxima
int distMax = -1;
// nodul din care pornest solutia
int solutie = -1;

// parcurge o data si gaseste solutia
int Solutie(int nod)
{
    // daca ndul nu a fost parcurs il parcurge
    if(!parcurs[nod])
    {
        int maxNod1 = -1;
        int maxVal1 = -1;
        int maxNod2 = -1;
        int maxVal2 = -1;

        parcurs[nod] = true;

        // cauta copiii acestui nod care au valorile
        // cele mai mari
        for(int i = 0; i < graf[nod].size(); i++)
        {
            // daca nodul nu a fost parcurs il parcurge
            // si ii afla valoarea
            int nod2 = graf[nod][i];
            if(!parcurs[nod2])
            {
                int val = Solutie(nod2);
                // daca e valoare maxima
                if(val >= maxVal1)
                {
                    // schimba a doua valoare maxima
                    maxVal2 = maxVal1;
                    maxNod2 = maxNod1;
                    maxVal1 = val;
                    maxNod1 = nod2;
                }
                else
                {
                    if(val >= maxVal2)
                    {
                        maxVal2 = val;
                        maxNod2 = nod2;
                    }
                }
            }
        }

        // calculeaza valoarea drumului maxim in punct
        int dist = 1;
        if(maxNod1 != -1)
        {
            dist += maxVal1;
            if(maxNod2 != -1)
                dist += maxVal2;
        }

        // daca e solutie
        if(dist > distMax)
        {
            distMax = dist;
            solutie = nod;
        }

        // calculeaza rezultatul in nod
        int result = 1;
        if(maxVal1 + 1 > result)
            result = maxVal1 + 1;
        
        return result;
    }

    return 0;
}

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    // citeste numarul de noduri si numarul de muchii
    fin >> n;

    // citeste muchiile si construieste graful
    for(int i = 0; i < n-1; i++)
    {
        // citeste muchia
        int nod1, nod2;
        fin >> nod1 >> nod2;
        // adauga nodurile in grad
        graf[nod1].push_back(nod2);
        graf[nod2].push_back(nod1);
    }

    // presupune ca nodul 1 este radacina arborelui. Programul
    // presupune ca agraful chiar are structura de arbore (este aciclic, neorientat si
    // conex)
    Solutie(1);

    // afiseaza distanta maxima
    fout << distMax << endl;

    fout.close();
    fin.close();

    return 0;
}
// Complexitate O(n). Algoritmul parcurge fiecare copil si afla lungimea de
// la el pana la cea mai departata frunza si verifica daca acea
// lungime + lungimea altui copil pana la cea mai departata frunza constituie
// solutia. Dupa ce gaseste solutia o parcurge.