Cod sursa(job #2246047)

Utilizator paul_danutDandelion paul_danut Data 26 septembrie 2018 15:36:43
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <queue>
#include <stack>
#include <tuple>
#include <list>
#include <algorithm>
//#include <iostream>

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

std::pair<size_t, size_t> findDiameter(std::list<size_t> tree[], size_t nodeId)
{
    auto max1 = 0U;
    auto max2 = 0U;

    std::for_each(tree[nodeId].cbegin(), tree[nodeId].cend(),[&tree, &max1, &max2](auto id){
           const auto p = findDiameter(tree, id);
           if(p.first > max1)
           {
               max2 = max1;
               max1 = p.first;
           }
           else
           {
               if(p.first > max2)
               {
                   max2 = p.first;
               }
           }
    });


    auto diameter = max1 + max2 + 1;

    //std::cout << "max1:" << max1 << ' ' << "max2:" << max2 << "diameter:" << diameter <<'\n';
    return std::make_pair(max1+1, diameter);
}

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

    std::list<size_t> tree[2*n];

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

        tree[x].push_back(y);
    }

    const auto p = findDiameter(tree, 1);
    fout << p.second <<'\n';

    return 0;
}