FasterHarder:


-----------------------------
Akina, приведи граф, где на твой взгляд важен порядок ходов и цвет как-то особо нужно учитывать. Я считаю, не сможешь привести)

Добавлено 16.03.21, 10:08
Подытожим алгоритм! Кому не лень и несложно, плиз проверьте + поправьте, если что.

1. находим все возможные тупики от заданной вершины. Всего в графе N вершин. Будет одномерный массив, состоящий из N элементов. У тупиков будут стоять 1цы, у остальных 0. Поиск тупиков через ДФС(стек)
2. помечаем все тупики статусом "победа"
3. инвертируем дуги исходного графа!
4. в цикле перебираем все тупики и от каждого тупика запускаем BFS (очередь). Помечаем чередованием вершины статусом "победа-поражение". ВАЖНО! Если встретилась вершина со статусом "победа", а ей для данного пути надо поставить статус "поражение", то ставим "поражение", т к у "поражения" высочайший приоритет. Также не меняем статус "поражение" на "победа" при возникновении обратной ситуации. Есть такой момент здесь: при обходе BFS будет задействовано много "лишних" вершин, которые не принадлежат ни одному из возможных путей. Это некритично - не обращаем на это внимания) На самом деле не оч.понятно, в какой момент заканчивать BFS, запущенный от текущего тупика. Ладно, пусть работает до упора - это НЕ оптимально и здесь можно как-то усовершенстовать.
5. после назначения статуса "победа-поражения" смотрим смежные вершины от стартовой. Если есть хотя бы одна вершина со статусом "победа" - победил игрок №1, иначе игрок №2.

Для статуса "победа-поражение", наверное, завести отдельный одномерный массив из N элементов (0 - поражение, 1 - победа). По дефалту поставить всем статус = 1.
язык Си, никаких STL-ских (делающих всю работу) приблуд

примерно так

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845451