lab5_ads
Laboratory work #5
Algorithms and data structures, ITMO, 4th semester
Вариант 8
Некоторые школы связаны компьютерной сетью. Между школами заключены соглашения: каждая школа имеет список школ получателей, которым она рассылает программное обеспечение всякий раз, получив новое бесплатное программное обеспечение (извне сети или из другой школы). При этом, если школа В есть в списке получателей школы А, то школа А может и не быть в списке получателей школы В. Требуется написать програму, определяющую минимальное количество школ, которым надо передать по экземпляру нового программного обеспечения, что бы распространить его по всем школам сети в соответствии с соглашениями (подзадача А). Кроме того, надо обеспечить возможность рассылки нового программного обеспечения из любой школы по всем остальным школам. Для этого расширить списки получателей некоторых школ, добавляя в них новые школы. Требуется найти минимальное суммарное количество расширений списков, при которых программное обеспечение из любой школы достигло бы остальных школ (подзадача В). Одно расширение означает добавление одной новой школы-получателя в список получателей одной из школ.Входные данные
Первая строка файла INPUT.TXT содержит целое число N - количество школ в сети (2<=N<=100). Школы нумеруются первыми N положительными целыми числами. Каждая из следующих N строк задает список получателей. Строка i+1 содержит номера получателей i-й школы. Каждый такой список заканчивается нулем. Пустой список содержит только 0.
Выходные данные
Ваша программа должна записать 2 строки в файл OUTPUT.TXT. Его первая строка должна содержать одно положительное целое число - решение подзадачи А. Вторая строка должна содержать решение подзадачи B.
Пример ввода и вывода
INPUT.TXT
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT.TXT
1
2