[Baekjoon] 11725. ツリーの親を検索[2]

5245 ワード
バックアップアルゴリズム テキストリンク

📚 質問する


https://www.acmicpc.net/problem/11725
方向のないグラフィックを接続する2 Dアレイを作成します.
親ノードの配置を初期化します.
BFSに移動します.まず、ツリーのルートノード1をキューにロードします.
1から取り出して確認し、子ノードの親ノード値を1に変更します.
各値を取り出し、各接続ノードの親ノード値をキューから取り出した値として入れます.
親ノードに0より大きい値が含まれている場合、確認された値は再確認せずに次の値に進みます.

📒 コード#コード#

from collections import deque


n = int(input())
arr = [[] for _ in range(n + 1)]

for i in range(n - 1):
    v1, v2 = map(int, input().split())
    arr[v1].append(v2)
    arr[v2].append(v1)

par = [0 for _ in range(n + 1)]

queue = deque()
queue.append(1)
par[1] = -1
while queue:
    v = queue.popleft()
    for v2 in arr[v]:
        if par[v2] == 0:
            queue.append(v2)
            par[v2] = v

for i in range(2, n + 1):
    print(par[i])

🔍 結果


[伯俊]10809 Python(アルファベット検索)
【伯俊】1157 Python(単語学習)