BOJ 11725ツリーの親を検索

https://www.acmicpc.net/problem/11725
1秒、256 MBメモリ
input :

N (2 ≤ N ≤ 100,000)

a b(ツリーに接続された2つの頂点)

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])