문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력 조건

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

전체 코드

import sys
sys.setrecursionlimit(10**5)

n = int(sys.stdin.readline().rstrip())

graph = dict()

for i in range(n):
    graph[i + 1] = []

# 양방향 그래프로 만든다.
for i in range(n - 1):
    u, v = list(map(int, sys.stdin.readline().split()))
    graph[u].append(v)
    graph[v].append(u)

parents = [0 for i in range(n + 1)]

# 루트의 부모는 자기 자신이다.
parents[1] = 1


# current = 현재 노드
def recursion(current: int):
    # 현재 노드와 인접한 노드들을 살펴본다.
    for adj_node in graph[current]:
        # 인접한 노드의 부모가 아직 안 정해져있다면, 현재 노드를 인접한 노드의 부모로 설정한다.
        # 그리고 인접한 노드를 현재 노드로 하여 다음 분기를 살핀다.
        if parents[adj_node] == 0:
            parents[adj_node] = current
            recursion(adj_node)


recursion(1)

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