Обсуждение @ 1218. Episode N-th: The Jedi Tournament @ Timus Online Judge

Nikita Mogilevets Небольшой хак для DFS [1] // Задача 1218. Episode N-th: The Jedi Tournament 23 июл 2017 18:16

Если вы используете DFS в итеративной форме, то вы можете получить TLE#4.

Если вы перепишите DFS в рекурсивную форму и будете компилировать на Visual C++, то получите AC за менее чем 0.1 секунды.

Nikita Mogilevets Re: Небольшой хак для DFS // Задача 1218. Episode N-th: The Jedi Tournament 23 июл 2017 18:19

Алгоритм свой я оцениваю как O(N*N*N) по времени,
Поскольку я N раз запускаю DFS по графу в котором O(N*N) ребер
(В графе проведено ребро от джедая который может победить джедая X в схватке к джедаю Х)

Обсуждение задачи 1218. Episode N-th: The Jedi Tournament