Cod sursa(job #2246024)

Utilizator paul_danutDandelion paul_danut Data 26 septembrie 2018 14:12:46
Problema Diametrul unui arbore Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <queue>
#include <stack>
#include <tuple>

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

int findDiameter(std::queue<size_t> tree[], size_t root, size_t n)
{
    std::stack< std::tuple< size_t, size_t, size_t > > st;
    int diameter = 0;

    st.push(std::make_tuple(root, 0U, 0U));
    while(!st.empty())
    {
        const auto nodeId = std::get<0>(st.top());
        if(!tree[nodeId].empty())
        {
            st.push(std::make_tuple(tree[nodeId].front(), 0, 0));
            tree[nodeId].pop();
        }
        else
        {
            diameter = std::get<1>(st.top()) + std::get<2>(st.top()) + 1;

            const auto max = std::max(std::get<1>(st.top()), std::get<2>(st.top()));
            st.pop();

            if(!st.empty())
            {
                auto& value = std::get<1>(st.top()) < std::get<2>(st.top()) ?
                              std::get<1>(st.top()) : std::get<2>(st.top());

                value = value <= max ? max + 1 : value;
            }
        }
    }

    return diameter;
}

int main()
{
    auto n = 0U;
    auto x = 0U;
    auto y = 0U;
    fin>>n;

    std::queue<size_t> tree[n+1];

    while(true)
    {
        fin >> x;
        fin >> y;
        if( fin.eof() ) break;

        tree[x].push(y);
    }

    const auto diameter = findDiameter(tree, 1, n);
    fout << diameter <<'\n';

    return 0;
}