[알고리즘/백준] 11725번 : 트리의 부모 찾기(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])

좋은 웹페이지 즐겨찾기