[Python] BOJ 11725 : 트리의 부모 찾기

요구사항

1. 시간제한
   1. N이 10만개 까지 가능하니 O(N) 이여야 한다. 
2. 메모리 제한 256MB 
3. 루트 노드는 1번이다.
4. 루트 노드를 제외한 노드들의 부모를 출력해라.
5. 2~7번 노드의 부모 노드를 한 줄에 하나씩 출력

설계

1. 노드 개수 N을 입력 받는다.
2. 인접한 노드들을 N-1 개 입력 받는다.
3. parent 값을 넣을 리스트를 초기화 한다. 
4. dfs 함수를 만든다.
   1. 단, 여기서 인자로 들어간 노드가 부모 노드이다. 
5. 1이 루트 노드이니 dfs(1) 을 해주자.
6. for 문을 통해 parent 리스트를 한 줄에 하나씩 출력하자.
   1. 단, parent의 0, 1 번 인덱스를 제외
   2. 0번과 1번은 빈 리스트이기 때문에.
   3. 왜? 0번은 숫자 맞추려고
   4. 1번은 루트 노드이기 때문에 부모가 없다. 

구현

import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
visited = [False] * (N + 1)
graph = [[] for _ in range(N+1)]

for i in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
parent = [[] for _ in range(N+1)]

def dfs(v):
    visited[v] = True
    
    for i in graph[v]:
        if not visited[i]:
            parent[i] = v
            visited[i] = True
            dfs(i)
dfs(1)

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