Pagini recente » Cod sursa (job #228267) | Cod sursa (job #2636403) | Cod sursa (job #2538034) | Cod sursa (job #2883911) | Cod sursa (job #2246022)
//#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <tuple>
#include <algorithm>
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;
//std::cout<<std::get<1>(st.top()) << ' ' << std::get<2>(st.top()) << '\n';
//std::cout<<diameter<<'\n';
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;
//std::cout<< "x: " << x << ' ' << "y: " << y << '\n';
tree[x].push(y);
}
/*for(auto i = 1U; i <= n; ++i)
{
std::cout<<i <<": ";
std::for_each(tree[i].begin(), tree[i].end(), [](auto j){
std::cout<< j <<' ';
});
std::cout<<'\n';
}*/
auto diameter = findDiameter(tree, 1, n);
fout << diameter <<'\n';
return 0;
}