Черепаха(#1062) Агенты(#1064)

#1063

Задача g6_1063: Михаил Густокашин против бюрократии
Задача классическая. Формулировка: Михаил Густокашин.

Как я уже писал, с 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

Решение g6_1063:
Эта задача - классическая. Именно с нее я начал свое изучение теории графов (никогда их не знал). Связи удобно представить в виде ориентированного графа:

Здесь нарисованы четыре кружочка со стрелочками. А могла бы быть ваша реклама!

Логично, что кружочек, в который не входит стрелочек можно смело убрать (записав его в список обхода, предварительно). Этот врач ничего не требует. Вместе с кружочком уберем и стрелочки, которые ведут от него. Эту операцию будем повторять, до тех пор, пока совсем не останется кружочков (я добыл все автографы!) или пока в результате операции не будет удалено ни одного кружочка (где-то возник цикл), т.е. все подписи получить невозможно.
Требования врачей удобно хранить в двумерном массиве K * K (таблице смежности). Если элемент a[x, y] = 1 - значит врачу x требуется справка врача y, если a[x, y] = 0, то врачу x справка врача y не требуется. Первоначально просматриваем все строки и ищем строки, в которых совсем нет единиц. Допустим, мы нашли, что такой строкой будет строка x. Теперь просматриваем столбец, с номером x, и все единицы заменяем в нем на нули (необходимая подпись получена).

Скачать тесты к задаче

Наверх