Такая задача:

Суть задачи: имеется компьютерная сеть из N пронумерованных компьютеров, некоторые компьютеры соединены между собой. В сети нет двух компьютеров, которые бы не были соединены хотябы через промежуточные (условие "Ы"). На указанном компьютере есть файл. Один компьютер одновременно может копировать файл только на один другой компьютер, с которым соединён. Время копирования файла - 1 минута. Необходимо скопировать этот файл на все компьютеры сети за минимальное количество времени. Задержки между операциями копирования не учитывать.

Входные данные: файл, в первой строчке которого содержиться два числа, разделённые пробелом: первое - количество компьютеров в сети, второе - номер компьютера, на котором содержиться файл изначально. Остальные строчки содержат по два числа, разделённых пробелом - эти пары чисел обозначают номера соединенных компьютеров. Известно что этот файл определяет сеть, удовлетворяющую условию "Ы". Нумерация компьютеров начинается с 1.

Выходные данные: файл, в последней строчке число - общее количество минут. В остальных строчках содержаться тройки чисел разделённых пробелом. Первое число указывает минуту с начала процесса копирования (первая минута - 1, вторая минута - 2). Второе число указывает номер компьютера, с которого файл копируется. Третье число указывает номер компьютера, на который производиться копирование файла. Если, например, в третью минуту три пары компьютеров производят копирование, то файл должен содержать три строки, у которых первое число будет 3.

Требуется: написать программу, которая по входному файлу получает выходной файл.

ЗЫ. На олимпиаде было дано ограничение на максимальное количество компьютеров в сети (точно не помню, но кажеться 64). Нужно попытаться без этого ограничения.

Пример:

Имеется сеть (звёздочкой обозначен компьютер, где изначально находиться файл):


Входной файл:


Выходной файл:


Это сообщение отредактировал(а) pompei - 13.12.2007, 07:15