Cod sursa(job #2428475)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 5 iunie 2019 15:20:28
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.81 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
    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;
}

int main()
{
    FILE* fin = fopen("darb.in", "r");
    FILE* fout = fopen("darb.out", "w");
    // citeste numarul de noduri si numarul de muchii
    fscanf(fin, "%d", &n);

    // citeste muchiile si construieste graful
    for(int i = 0; i < n-1; i++)
    {
        // citeste muchia
        int nod1, nod2;
        fscanf(fin, "%d %d", &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
    fprintf(fout, "%d", distMax);

    fclose(fout);
    fclose(fin);

    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.