트리의 부모 찾기
노드의 부모를 저장할 리스트 answer를 만든다.
(answer[2]의 값은 2번 노드의 부모)그 후 주어진 stack을 이용하여 입력대로 저장되어 있는 graph를 깊이 우선 탐색하며
각 노드의 부모를 구한다.처음에 문제를 이해하는데 시간이 조금 걸렸지만,
dfs를 이용하여 쉽게 풀 수 있었다.재밌다
N = int(input()) graph = {} for _ in range(N - 1): a, b = map(int, input().split()) if a in graph: if b not in graph[a]: graph[a].append(b) else: graph[a] = [b] if b in graph: if a not in graph[b]: graph[b].append(a) else: graph[b] = [a] answer = [0] * (N + 1) stack = [1] while stack: n = stack.pop() if answer[n]: continue if n in graph: if n == 1: answer[n] = -1 else: for v in graph[n]: if answer[v]: answer[n] = v temp = sorted(graph[n], reverse=True) stack.extend(temp) print(*answer[2:], sep='\n')