白駿11725号:木の親を探す

8134 ワード
python DFS ps テキストリンク

ツリーの親を検索


白駿11725号:木の親を探す

アイデア


DFSを使用してルートノード1からナビゲートを開始します.親-子の順序ではないことに注意して入力します.

コード#コード#

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())

visited = [False] * (N + 1)
graph = [[] for _ in range(N + 1)]
parents = [1] * (N + 1)

for _ in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(start):
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            parents[i] = start
            dfs(i)


dfs(1)
for n in range(2, N + 1):
    print(parents[n])

おしゃべり


最初はバカみたいに解けた
def findParent(c, p, t):
    if c == t:
        print(p)
        return
    visited[c] = True
    for i in graph[c]:
        if not visited[i]:
            findParent(i, c, t)


for target in range(2, N + 1):
    findParent(1, 0, target)
    visited = [False] * (N + 1)
    visited[1] = True
各ノードは関数を1回実行し、タイムアウトします.1つのノードの親ノードを探す問題ではなく、すべてのノードの親ノードを探す問題なので、ナビゲーションと同時に記録すればよい.これからは気をつけてね
[TIL] React : Live Async Validation
継承ではなくアセンブリ