Question

Вы разрабатываете сложную систему передачи данных через особые вышки сотовой связи – передатчики. Работает эта система так: 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

Answer 1

Для решения задачи можно воспользоваться свойством ориентированных графов: если существует путь из вершины 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)

Answer 2

Для решения данной задачи можно использовать алгоритм обхода графа в глубину (Depth-First Search, DFS). В данном случае граф представляет собой сеть передатчиков, а каждый передатчик является вершиной, а связи между передатчиками - ребрами.

Воспользуемся следующим планом:

1. Создадим пустой словарь transmitters, который будет хранить информацию о связях между передатчиками. Ключом будет номер передатчика, а значением - номер получателя сообщения.
2. Считаем число передатчиков N и заполним словарь transmitters согласно вводу.
3. Считаем номер стартового передатчика start.
4. Создадим функцию dfs, которая будет рекурсивно искать конечный передатчик. Функция будет принимать текущий передатчик current и проверять, является ли он конечным передатчиком. Если да, то вернем его номер. Если нет, то вызовем функцию dfs рекурсивно для передатчика, которому текущий передатчик передает сообщение.
5. В основной части программы вызовем функцию dfs для стартового передатчика и выведем полученный номер конечного передатчика.

Пример реализации на языке Python:

pythonCopy code
def dfs(current, transmitters):
    if current not in transmitters:
        return current
    return dfs(transmitters[current], transmitters)

# Считываем входные данные
N = int(input())
transmitters = {}
for _ in range(N - 1):
    from_, to = map(int, input().split())
    transmitters[from_] = to
start = int(input())

# Вызываем функцию dfs
end = dfs(start, transmitters)

# Выводим результат
print(end)

При запуске данного кода и вводе первого примера (4 2 3 3 1 1 4 2), будет выведено число 4, что является номером конечного передатчика. Аналогично, при вводе второго примера (5 1 4 4 5 3 1 2 3 2), будет выведено число 5.