Восстанови порядок
В очереди стояли n человек, у каждого из которых на футболке сзади написан свой собственный номер от 1 до n. На следующий день каждый помнил за кем именно он стоял, но не помнил состояние очереди в целом.
Вам необходимо по этой информации восстановить порядок стоявших в очереди людей.
Формат входных данных
В первой строке записано одно целое число n — количество людей в очереди (2≤n≤5⋅10^5). Следующие n−1 строк содержат по два разделённых пробелом целых числа a и b — номера на футболках стоявших рядом друг с другом людей, где a — номер на футболке человека, стоявшего перед человеком в футболке с номером b (1≤a,b≤n). Порядок этих пар произвольный.
Формат выходных данных
В единственной строке запишите через пробел n целых чисел — номера на футболках фанатов в порядке, в котором они стояли в очереди.
Если возможных порядков несколько, то выведите любой из них.
1 Ответ
Просто перебираем пары чисел на соответствие так, чтобы последняя цифра одной пары была идентична первой цифре следующей пары.
n = int(input())
a = {}
for _ in range(n-1):
a.update([tuple(map(int, input().split()))])
p = n*(n+1)//2
for i in a.values():
p -= i
ans = [p]
for i in range(n-1):
p = a[p]
ans.append(p)
print(*ans)
n = int(input())
a = {}
for _ in range(n-1):
~~~~a.update([tuple(map(int, input().split()))])
p = n*(n+1)//2
for i in a.values():
~~~~p -= i
ans = [p]
for i in range(n-1):
~~~~p = a[p]
~~~~ans.append(p)
print(*ans)