16940-BFS特別阻止
1247 ワード
from collections import deque
n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
answer = list(map(int, input().split()))
visit = [False] * (n + 1)
depth = [0] * (n + 1)
parent = [0] * (n + 1)
order = [0] * (n + 1)
for i in range(n):
order[answer[i]] = i
def dfs(node, d):
visit[node] = True
depth[node] = d
for next in graph[node]:
if not visit[next]:
dfs(next, d + 1)
parent[next] = node
dfs(1, 0)
for i in range(n - 1):
if depth[answer[i]] > depth[answer[i+1]]:
print(0)
break
if order[parent[answer[i]]] > order[parent[answer[i+1]]]:
print(0)
break
else:
print(1)
前提:BFSで巡回中に現在の頂点の深さを保存すると、配列は昇順にソートされます.上記の前提に基づいて問題を解き、いくつかの例外を処理しなければならない.
例外頂点の深さが同じでも、例外的に順序が間違っている場合を処理します.
このようなパターンでは、BFSにループした結果を1 3 2 4 5 6と呼び、それらの深さを表すと、深さは0 1 2の昇順で表される.
ただし、巡視1 3 2であれば6 4 5または6 5 4の順に巡視し、4 5 6であれば通常のBFS巡視ではない.
そこで,この問題を解決するために,現在のノードの親ノードの順序を比較して問題を解決した.
例外問題では,処理起点は1であるがBFS巡回結果は1で始まる例外ではない.
Reference
この問題について(16940-BFS特別阻止), 我々は、より多くの情報をここで見つけました https://velog.io/@suker80/16940-BFS-스페셜-저지テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol