У нас есть игра, в которой ничьих не бывает, и для каждой пары игроков мы знаем, кто кого выиграет. Наша задача — для каждого игрока определить, можно ли составить такое расписание турнира, чтобы этот игрок выиграл.

Боян? Добавим в условие дополнительное ограничение: на каждой стадии турнира каждый из игроков обязан сыграть с другим игроком (кроме игрока, для которого пара не нашлась — он автоматически проходит в следующую стадию).

Задачу в таком виде мне подкинул Jokser, вот источник (условия, задача D, тесты). К сожалению, авторское решение задачи соответствует решению оригинальной задачи без введения дополнительного ограничения (я так утверждаю, потому что разобрал тесты).

Задача смахивает на NP-полную, но такое впечатление иногда бывает обманчивым. Так можно ли все-таки решить ее за полиномиальное время? Если да, то как?

UPD. Интуитивные рассуждения приводят к тому, что задача должна быть NP-полной, т.к. сводится к чему-то вроде пересечения трех или более матроидов. Знатоки этой темы, откликнитесь...