Задача 40: Михаил Густокашин против
бюрократии
Задача
классическая. Формулировка: Михаил Густокашин.
Как я уже писал, с
1 сентября 2002 года я буду учиться в СУНЦ
МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того,
чтобы я был допущен к занятиям, мне необходимо предъявить справку по
форме 086/У, на которой должна поставить свои подписи K врачей.
Все было бы хорошо, но вот некоторые врачи отказываются ставить
подписи на справке до тех пор, пока на ней не распишется другой
врач. Например, стоматолог отказался ставить мне подпись, пока я не
принесу справку от психиатра, потому, что однажды его укусил один
психически неуравновешенный мальчик, да так, что бедному врачу
пришлось два месяца сидеть на больничном. Теперь он у всех своих
пациентов требует справку об отсутствии психических расстройств.
Много странностей у врачей...
Закончилось тем, что я составил список, какому врачу нужны какие
справки. В первой строке моего списка (input.txt) содержится общее
количество врачей (1 <= K <= 100). В следующих K строках описываются
необходимые справки. Первое число (j) в i+1 строке входного файла
означает, сколько справок нужно i-му врачу. Затем, в той же строке,
содержится j чисел - номера врачей, чьи подписи надо предварительно
поставить, чтобы получить подпись i-го врача.
Если подписи всех врачей собрать невозможно, то в выходной файл (output.txt)
следует вывести "NO". Если же все справки собрать возможно, то в
первой строке выходного файла должно содержаться "YES", а в
следующих K строках - последовательность, в которой нужно получать
справки.
Пример входного файла:
4
1 2
0
2 1 4
1 1
Пример выходного файла:
YES
2
1
4
3
Решение:
Эта задача - классическая. Именно с нее я начал свое изучение теории
графов (никогда их не знал). Связи удобно представить в виде
ориентированного графа:
Логично, что
кружочек, в который не входит стрелочек можно смело убрать (записав
его в список обхода, предварительно). Этот врач ничего не требует.
Вместе с кружочком уберем и стрелочки, которые ведут от него. Эту
операцию будем повторять, до тех пор, пока совсем не останется
кружочков (я добыл все автографы!) или пока в результате операции не
будет удалено ни одного кружочка (где-то возник цикл), т.е. все
подписи получить невозможно.
Требования врачей удобно хранить в двумерном массиве K * K (таблице
смежности). Если элемент a[x, y] = 1 - значит врачу x требуется
справка врача y, если a[x, y] = 0, то врачу x справка врача y не
требуется. Первоначально просматриваем все строки и ищем строки, в
которых совсем нет единиц. Допустим, мы нашли, что такой строкой
будет строка x. Теперь просматриваем столбец, с номером x, и все
единицы заменяем в нем на нули (необходимая подпись получена).
Далее
ð
