문제

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

풀이방법

트리의 입력순서가 루트노드부터 순서대로 입력되지 않는다는 점에 유의하면서 풀어야 한다.

• 노드와 연결된 모든 노드를 저장한다.
• 재귀함수를 이용하여 아직 방문하지 않은 노드들의 부모 노드를 저장해준다.

코드

import sys
sys.setrecursionlimit(10000000)
n=int(input())

tree=[[] for _ in range(n+1)]

for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    tree[a].append(b)
    tree[b].append(a)

parents=[0]*(n+1)

def back(node):
    for temp in tree[node]:
        if parents[temp]==0:
            parents[temp]=node
            back(temp)

    
parents[1]=1
back(1)
for i in range(2, n+1):
    print(parents[i])

연산 시간