백준 11725 트리의 부모 찾기 - 파이썬

문제.

풀이.

주어진 입력들을 양방향으로 연결하고 1에서 BFS를 실행하여 각 노드의 부모를 찾으면 된다.

 

소스코드.

import sys
from collections import deque
def BFS():
    answer = [0] * n
    visited = [False] * (n+1)
    queue = deque([1])
    while queue:
        parent = queue.popleft()

        for i in tree[parent]:
            if not visited[i]:
                answer[i-1] = parent
                queue.append(i)
                visited[i] = True
    return answer[1:]


input = sys.stdin.readline

n = int(input())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    x, y = list(map(int, input().split()))
    tree[x].append(y)
    tree[y].append(x)

answer = BFS()
for i in answer:
    print(i)