Задача 52: Замок (XIII Всероссийская олимпиада по информатике)
В замке Stonehandge юный принц не
поладил со своей гувернанткой в комнате, где они завтракали. Для
избежания наказания принц решил спрятаться в одной из комнат замка.
Двигаясь из комнаты в комнату, принц обязательно закрывал на ключ
дверь, через которую он прошел, после чего ни он, ни гувернантка не
могли воспользоваться этой дверью. Через любую комнату (в том числе
и через ту, в которой находится гувернантка) принц может проходить
несколько раз, если это позволяют еще не запертые им двери.
Изначально все двери замка не заперты.
Между двумя комнатами замка не более одной двери. Общее количество
дверей не превосходит 5000.
Гувернантка начинает искать принца только после того, как он
спрятался. Избежать наказания принц может только в том случае, если
гувернантка, проходя через оставшиеся незапертыми двери, не сумеет
попасть в комнату, где он спрятался.
Требуется
Написать программу, которая определяет, сможет ли принц спрятаться
от гувернантки, и если укрыться удается, то предлагает ему любой из
возможных путей спасения.
Входные данные
Во входном файле CASTLE.IN содержится план замка.
В первой строке входного файла находится натуральное число N (1 < N
< 1000) - количество комнат.
Во второй строке входного файла содержится натуральное число K (1 <=
K <= N) - номер комнаты, в которой принц и гувернантка завтракали.
В последующих N строках содержатся списки смежных комнат: в i-й
строке перечислены через пробел номера комнат, смежных с i-й
комнатой. Каждая такая строка заканчивается нулем.
Выходные данные
Выходной файл с именем CASTLE.OUT должен содержать следующую
информацию. Если принц не сможет избежать наказания, в единственной
строке файла выводится сообщение No. В противном случае в первой
строке файла выводится сообщение Yes, во второй строке - количество
дверей, закрытых принцем, а в третьей строке - последовательность
номеров комнат, разделенных пробелами, в которых побывал принц.
Пример входного файла
4
1
2 4 0
4 1 3 0
2 4 0
1 2 3 0
Пример выходного файла для приведенного примера входного
файла
Yes
3
1 4 2 3
Примечание. Будут отдельно оцениваться решения для частного
случая N <= 100.
Решение: предоставлено
Е.В. Андреевой
Несмотря на то что условие задачи легко переформулировать в терминах
теории графов, ее решение не сводится полностью ни к одному из
стандартных алгоритмов на графах, а основано на здравом смысле. Во
первых, следует исключить из рассмотрения комнаты, до которых
невозможно добраться из комнаты, в которой принц завтракал с
гувернанткой, т.е. выделить компоненту связности графа, например, с
помощью ее обхода в глубину или в ширину. Если выделенная компонента
связности графа состоит только из начальной комнаты или содержит
эйлеров цикл, то есть комнаты возможно обойти, обязательно проходя
через каждую из дверей ровно один раз (при этом в любой из комнат
можно бывать сколько угодно раз), то спрятаться в таком замке
невозможно. Согласно известной теореме, несложно проверить, обладает
ли граф таким свойством - необходимым и достаточным условием наличия
эйлерова цикла в графе является условие четности степеней всех его
вершин, то есть в каждой из комнат, включая начальную, должно быть
четное число дверей.
В противном случае в замке спрятаться можно. Если в начальной
комнате нечетное число дверей, то двигаться принцу можно в
произвольном направлении либо до тех пор, пока он не окажется в
комнате, все двери в которую уже заперты, либо пока принц не
вернется в комнату, с которой он начал движение, и в ней незапертой
останется ровно одна дверь. Тогда ему следует войти в эту дверь, и
изолированной окажется уже гувернантка, что также является для
принца спасительным вариантом. Если же в начальной комнате четное
число дверей, то принцу следует сначала добраться до любой из
комнат, количество дверей в которой нечетно, затем пройти по всем
существующим циклам, которые начинаются и заканчиваются в этой
комнате. В результате либо принц уже окажется запертым в такой
комнате, либо по крайней мере одна из оставшихся двух, четырех и
т.д. дверей уже не будет связана с начальной комнатой. Когда принц
пройдет через нее и запрет ее за собой, гувернантка добраться до
него уже не сможет. Если бы такой двери не существовало, то есть из
всех оставшихся незапертыми дверей все еще можно было бы вернуться в
исходную комнату, то это означало бы наличие по крайней мере еще
одного цикла. Таким образом, задача решена для всех случаев.
Далее
ð
