Pagini recente » Borderou de evaluare (job #1036558) | Cod sursa (job #1377984) | Cod sursa (job #2146891) | Cod sursa (job #1557302) | Cod sursa (job #2246052)
#include <fstream>
#include <stack>
#include <tuple>
#include <list>
#include <algorithm>
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;
auto diameter = 0U;
std::for_each(tree[nodeId].cbegin(), tree[nodeId].cend(),[&tree, &max1, &max2, &diameter](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;
}
}
if(p.second > diameter)
{
diameter = p.second;
}
});
auto local_diameter = max1 + max2 + 1;
if(diameter < local_diameter)
{
diameter = local_diameter;
}
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[n+1];
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;
}