(Python)[백준] 트리의 부모 찾기_11725

문제

---

11725번: 트리의 부모 찾기

풀이

---

from typing import List
import sys

# 자기 호출 개수 제한. 안하면 메모리 초과..ㅂㄷ
# Python3의 기본 재귀 깊이가 1000이므로 재귀깊이를 해제한다
sys.setrecursionlimit(10**6)
# 안하면 시간 초과..ㅂㄷ
input=sys.stdin.readline

# 노드의 개수
N = int(input())
# 2차원 리스트(인접 행렬)
graph = [[] for _ in range(N+1)] # 1부터 시작하므로 n+1
# 노드의 부모를 기록하는 리스트
visited = [0] * (N+1)

# 트리 상에서 연결된 두 정점 입력 받기
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(graph: List[int], vertex: int, visited: List[int]):
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[vertex]:
        if not visited[i]:
            visited[i] = vertex # 부모 노드를 저장
            dfs(graph, i, visited)

# 1의 부모는 1
visited[1] = 1
dfs(graph, 1, visited)

for i in range(2, N+1):
    print(visited[i])