Open nagato1208 opened 5 years ago
https://nagato1208.github.io/2019/09/08/codeforces-1037D-Valid-BFS/#more
描述给一个任意的树(任意的无向无环图), 和一个节点序列. 判断这个序列是否是一种以节点1为入口的BFS序列. 思路层序BFS模拟一遍. 有趣的一点是, 本题我们不记录节点的childen, 而是记录他们的parent(s). 对于当前层中的每个点, 检查他们的parents(last)是不是有序的. 如果parents(last)一直有序并且走到头, 那么另起一层, 上层的节点们作为新的par
https://nagato1208.github.io/2019/09/08/codeforces-1037D-Valid-BFS/#more
描述给一个任意的树(任意的无向无环图), 和一个节点序列. 判断这个序列是否是一种以节点1为入口的BFS序列. 思路层序BFS模拟一遍. 有趣的一点是, 本题我们不记录节点的childen, 而是记录他们的parent(s). 对于当前层中的每个点, 检查他们的parents(last)是不是有序的. 如果parents(last)一直有序并且走到头, 那么另起一层, 上层的节点们作为新的par