[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬

[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬

[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

풀이

각 node의 root를 찾는 문제이다.

 

최상단의 root 노드가 항상 1로 시작하기 때문에,

모든 edge 를 기록한뒤 1부터 Tree 를 내려가며 root 를 기록하였다.

 

from collections import deque
N = int(input())

graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    f, t = map(int, input().split())
    graph[f].append(t)
    graph[t].append(f)

parenRoot = [0] * (N+1)


dq = deque()
dq.append(1)

while dq:
    n = dq.popleft()

    for m in graph[n]:
        if not parenRoot[m]:
            parenRoot[m] = n
            dq.append(m)


for p in parenRoot[2:]:
    print(p)