Pagini recente » Cod sursa (job #527729) | Cod sursa (job #2913179) | Cod sursa (job #2645073) | Cod sursa (job #2384729) | Cod sursa (job #2246024)
#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;
}