Вы разрабатываете сложную систему передачи данных через особые вышки сотовой связи – передатчики. Работает эта система так:
0. Все передатчики занумерованы числами от 1 до N.
1. Есть стартовый и конечный передатчики.
2. На стартовый вы отправляете сообщение, после чего он пересылает сообщение какому-то другому передатчику
3. Как только промежуточный передатчик получает сообщение, он также пересылает его новому передатчику
4. Этот процесс будет происходить, пока сообщение не дойдет до конечного передатчика
Чтобы система работала быстро и стабильно, вы решили для каждого передатчика заранее зафиксировать, кому он будет пересылать сообщение. Причем это конкретный номер.
Вам известно для каждого из передатчиков номер передатчика – получателя сообщения
К сожалению, вы забыли номер конечного передатчика, но по-прежнему обладаете информацией о номере стартового
Восстановите номер конечного передатчика, зная номер стартового.
Формат ввода
В начале идет число N (1 ≤ N ≤ 105) – количество передатчиков. Далее идет N - 1 строка. Каждая строка состоит из двух чисел from и to (1 ≤ from, to ≤ N), которая означает, что передатчик под номером from всегда передает сообщение передатчику под номером to. В конце идет число start (1 ≤ start ≤ N) – номер стартового передатчика.
Формат вывода
Выведите одно единственное число – номер конечного передатчика
Пример 1
Ввод
4
2 3
3 1
1 4
2
вывод
4
Пример 2
Ввод
5
1 4
4 5
3 1
2 3
2
вывод
5
Примечания
Рассмотрим 2 тест
Пусть сообщения будет следующим
2 -> 3 -> 1 -> 4 -> 5
Поэтому ответ – 5
Ответы
Для решения задачи можно воспользоваться свойством ориентированных графов: если существует путь из вершины a в вершину b, то вершина b достижима из вершины a. Это свойство позволяет обойти граф, начиная с заданного стартового узла, и найти все достижимые узлы.
Алгоритм решения задачи:
Считываем число N и создаем пустой словарь соответствий номеров передатчиков и номеров получателей.
Считываем N-1 строку входных данных и добавляем в словарь соответствие номера передатчика и номера получателя.
Считываем номер стартового передатчика.
Находим конечный передатчик, применяя свойство ориентированных графов: начиная с номера стартового передатчика, последовательно переходим к передатчику, указанному в словаре соответствий, пока не найдем такой, у которого нет указания на следующий передатчик.
Выводим номер найденного передатчика.
Реализация алгоритма на Python:
n = int(input())
graph = {}
for i in range(n-1):
from_node, to_node = map(int, input().split())
graph[from_node] = to_node
start = int(input())
current_node = start
while current_node in graph:
current_node = graph[current_node]
print(current_node)