[アルゴリズム/標準]1725号:ツリーの親を検索(python)
1がスタートなので、1からbfsを回せばいいです.
from collections import deque
N = int(input())
visited = [0] * (N + 1)
ans = [0] * (N + 1)
a = dict()
for i in range(1, N + 1):
a[i] = set()
for i in range(N-1):
x, y = map(int, input().split())
a[x].add(y)
a[y].add(x)
q = deque()
q.append((1))
while q:
x = q.popleft()
for i in a[x]:
if visited[i] != 1:
ans[i] = x
q.append(i)
visited[i] = 1
for i in range(2, N+1):
print(ans[i])Reference
この問題について([アルゴリズム/標準]1725号:ツリーの親を検索(python)), 我々は、より多くの情報をここで見つけました https://velog.io/@y7y1h13/알고리즘백준-11725번-트리의-부모-찾기pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol