[BOJ]白駿11725号樹を見つけた両親(Python)

10372 ワード
白駿 boj BFS DFS tree algorithm Graph テキストリンク

質問する


根のない木をあげます.ツリーのルートディレクトリが1の場合、各ノードの親ノードを解くプログラムを作成します.

入力


第1行は、ノード数N(2≦N≦100000)を与える.2行目から、ツリーに接続された2つの頂点がN−1行に与えられる.

しゅつりょく


1行目からN-1行目まで、各ノードの親ノード番号が2番目のノードから順次出力されます.

例


入力します。

7
1 6
6 3
3 5
4 1
2 4
4 7

出力します。

4
6
1
3
1
4

入力します。

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

出力します。

1
1
2
3
3
4
4
5
5
6
6

に答える


DFS

import sys

# recursion error 떠서 recursion limit 늘려줌
sys.setrecursionlimit(10 ** 9)

def DFS(start):
    for i in Tree[start]:
        if Parent[i] == 0:
            Parent[i] = start
            DFS(i)

n = int(sys.stdin.readline())

Tree = list(list() for _ in range(n+1))
Parent = list(0 for _ in range(n+1))

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

Parent[1] = -1
DFS(1)

for x in Parent[2:]:
    print(x)
最初はDFSを使用して解凍したが、エラーが返されたため実行が中断した.従って、sys.setrecursionlimit(10 ** 9)コードにより再帰限界が増加する.
しかし,これらの誤りを回避するためにDFSではなくBFSの使用も試みた.

BFS

import sys
from collections import deque

n = int(sys.stdin.readline())
Tree = list(list() for _ in range(n+1))
Parent = list(0 for _ in range(n+1))

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

queue = deque([1])

while queue:
    tmp = queue.popleft()
    for i in Tree[tmp]:
        if Parent[i] == 0:
            Parent[i] = tmp
            queue.append(i)


for x in Parent[2:]:
    print(x)

結果



上はBFS、下はDFSを使った結果です.DFSは戻りエラーが発生したが,戻り制限が増加するとBFSよりも結果が速くなる.
Matplotlib with Pandas
NestJSとGraphQL CRUDを試してみてください