Cod sursa(job #2861510)

Utilizator PalffyLehelPalffy Lehel PalffyLehel Data 4 martie 2022 08:54:42
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>

using namespace std;

int main()
{
    ifstream f("darb.in");
    ofstream g("darb.out");

    int n;
    f >> n;

    list<int> csucsok[n];
    list<int> :: iterator it;

    int x, y;
    for (int i = 0; i < n; i++)
    {
        f >> x >> y;

        csucsok[x - 1].push_back(y - 1);
        csucsok[y - 1].push_back(x - 1);
    }

    bool jart[n];
    fill_n(jart, n, false);
    jart[0] = true;

    int hossz[n];
    fill_n(hossz, n, 1);

    stack<int> sor;
    sor.push(0);

    int elem;
    while(!sor.empty())
    {
        elem = sor.top();
        sor.pop();

        for (it = csucsok[elem].begin(); it != csucsok[elem].end(); it++)
        {
            if (!jart[*it])
            {
                hossz[*it] = hossz[elem] + 1;
                jart[*it] = true;

                sor.push(*it);
            }

        }
    }

    int maxi = 0, index = 0;
    for (int i = 0; i < n; i++)
    {
        if (maxi < hossz[i])
        {
            maxi = hossz[i];
            index = i;
        }
    }


    fill_n(jart, n, false);
    jart[index] = true;
    fill_n(hossz, n, 1);

    sor.push(index);

    while(!sor.empty())
    {
        elem = sor.top();
        sor.pop();

        for (it = csucsok[elem].begin(); it != csucsok[elem].end(); it++)
        {
            if (!jart[*it])
            {
                hossz[*it] = hossz[elem] + 1;
                jart[*it] = true;

                sor.push(*it);
            }
        }
    }

    maxi = 0;
    for (int i = 0; i < n; i++)
    {
        if (maxi < hossz[i])
        {
            maxi = hossz[i];
        }
    }

    g << maxi;

    return 0;
}