Форум DL

Мой профиль

Sp105
code: ALICEBOB
Есть правильный N-угольник. Нам даны все стороны этого многоугольника. И некоторые диагонали. Причём нам известно, что данные нам диагонали НЕ пересекаются(диагонали имеющие общую вершину не считаются пересекающимися). (На вводе множество пар чисел -номера вершин соединённых стороной или диагональю)
Требуется определить порядок вершин этого многоугольника.
20 тестов
N<10000
M(количество диагоналей)<n-3

Решение.
Фактически нам надо найти Гамильтонов цикл. Во первых если в найденном нами цикле есть хотя бы одна диагональ то длина нашего цикла будет меньше N. Тк диагональ пропускает хотя бы одну вершину и посетить ее мы больше не сможем тк диагонали НЕ пересекаются. Во вторых если в цикле есть ребро соединяющее вершины A и B и существует путь из A в B по которому мы можем увеличить цикл то ребро соединяющее a и b - Диагональ.
и обратное для любой диагонали найдётся путь её заменяющий.
при этом этот путь увеличит кол-во посещённых вершин.
Следовательно можно использовать такой алгоритм:
Найдём любой цикл.
Для каждого ребра входящего в цикл будем искать увеличивающий путь и дополнять цикл, при этом длина цикла будет увеличиваться.
При этом ЛЮБОЙ цикл можно дополнить до гамильтонова.

______________________
=====