BOJ 11725 트리의 부모 찾기

https://www.acmicpc.net/problem/11725
시간 1초, 메모리 256MB
input :

• N (2 ≤ N ≤ 100,000)
• a b(트리 상에서 연결된 두 정점)

output :

• 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력

조건 :

• 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램

---

양방향 그래프를 저장하듯 인접리스트에 저장을 하자.

graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

parent 1차원 리스트를 만들어서 저장을 하자.
parent는 자기자신으로 초기화를 해둠.

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

해서 자기자신을 가르키지 않을 경우엔 이미 방문을 한 것.
visit 대신에도 사용할 수 있다.

import sys
from _collections import deque

n = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
parent = [i for i in range(n + 1)]

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

def BFS():
    start = 1
    q = deque([start])
    while q:
        now = q.popleft()
        for next_node in graph[now]:
            if parent[next_node] == next_node:
                parent[next_node] = now
                q.append(next_node)

BFS()
for i in range(2, len(parent)):
    print(parent[i])