题解 CodeForces 1037D Valid BFS? 三种解法 C++

题目传送门

Problem - 1037D - Codeforceshttps://codeforces.com/problemset/problem/1037/Dhttps://codeforces.com/problemset/problem/1037/Dhttps://codeforces.com/problemset/problem/1037/Dhttps://codeforces.com/problemset/problem/1037/Dhttps://codeforces.com/problemset/problem/1037/Dhttps://codeforces.com/problemset/problem/1037/Dhttps://codeforces.com/problemset/problem/1037/D

翻译

广度优先搜索（BFS）算法定义如下。

考虑一个无向图，顶点编号从 1 到 n。初始化 q 为一个新的队列，仅包含顶点 1，并将顶点 1 标记为已使用。
从队列 q 的头部提取一个顶点 v。
打印顶点 v 的索引。
以任意顺序遍历所有与 v 相邻且尚未标记为已使用的顶点 u。将顶点 u 标记为已使用，并将其插入到队列 q 的尾部。
如果队列不为空，从第 2 步继续。
否则结束。

由于选择每个顶点的邻居的顺序可以变化，因此可能存在多个序列可以被 BFS 打印。

在这个问题中，你需要检查给定的序列是否对应于从顶点 1 开始的给定树的某个有效 BFS 遍历。树是一个无向图，任意两个顶点之间恰好有一条简单路径。

输入

第一行包含一个整数 n (1≤n≤2⋅10^5)，表示树中的节点数量。

接下来的 n−1 行描述树的边。每行包含两个整数 x 和 y (1≤x,y≤n) — 对应边的两个端点。保证给定的图是树。

最后一行包含 n 个不同的整数 a1,a2,…,an (1≤ai≤n) — 要检查的序列。

输出

如果该序列对应于给定树的某个有效 BFS 遍历，则打印 "Yes"（引号仅为清晰），否则打印 "No"（引号仅为清晰）。

你可以使用任意大小写打印每个字母（大写或小写）。

示例

Inputcopy	Outputcopy
4 1 2 1 3 2 4 1 2 3 4	Yes

Inputcopy	Outputcopy
4 1 2 1 3 2 4 1 2 4 3	No

注意

两个示例测试中包含相同的树。

在这棵树中，有两个有效的 BFS 排序：

1,2,3,4
1,3,2,4

排序 1,2,4,3 不对应于任何有效的 BFS 排序。

解法

易错点解读

连续节点并非同层就行，还有一个重要的点是，子树顺序要与父节点顺序对应

如：1 2 3 [2 的子节点] [3 的子节点] 才行，1 2 3 [3 的子节点] [2 的子节点] 就不行

解法一览

1.按输入顺序生成 BFS 序列，比较输入序列与生成序列 (比较好理解)

2.循环模拟队列

1) for 循环模拟队列 (比较抽象，代码精简)

2) while 循环模拟队列 (有点抽象)

三种解法效率差不多，250~350ms (前提是经过优化且采用较快的 I/O 方式)

一、按输入顺序生成 BFS 序列，比较输入序列与生成序列

思路

BFS 序列可能有很多，根本原因如题目所说 "选择每个顶点的邻居的顺序可以变化"

即同层节点，入队的顺序有很多种

那我们可以按题目给出的序列重定义入队顺序，对于某节点的子节点

先在序列中出现，就先入队，比较生成的 BFS 序列与所给序列是否相同即可

细节见代码注释

代码

#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 200010;
vector<int> g[N];
int n, x, y, q[N], idx[N], ans[N], head, tail = -1; //q 是输入的队列，ans 是生成的队列，idx 是优先级
bool mk[N];
bool cmp(int a, int b) { return idx[a] < idx[b]; } //重定义入队优先级，先输入的就先入队
int main()
{scanf("%d", &n);for (int i = 1; i < n; i++){scanf("%d%d", &x, &y);g[x].push_back(y);g[y].push_back(x);}for (int i = 0; i < n; i++) scanf("%d", &q[i]), idx[q[i]] = i; //先输入的下标更小，更先入队if (idx[1] != 0) return puts("No") * 0; //需要特判第一个元素for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end(), cmp); //按入队优先级对子节点排序ans[++tail] = 1; //生成队列初始化mk[1] = true;while (head <= tail){int t = ans[head++];for (auto z : g[t]){if (mk[z] == false) //因为是无向边，子节点可以通向父节点，为避免父节点入队子节点后子节点又入队父节点，开标记数组，入队过就不再入队了{ans[++tail] = z;if (q[tail] != ans[tail]) return puts("No") * 0; //两个序列有任何差异都输出 Nomk[z] = true;}}}return puts("Yes") * 0; //无差异输出 Yes
}

二、for 循环模拟队列

思路

根据输入的节点序列，用 for 循环模拟队列

设节点序列为 node[N]，队首为 head，队尾为 tail

和一般队列不同的是，在此处 tail 指向下一个要入队的节点

也就是指向当前真正的队尾的下一个节点

每轮循环的任务：入队队首的所有子节点，然后队首出队

对于合法的 BFS 序列，每次循环体执行前

从 tail 开始的向后的一片连续节点都来自同一层，且子树顺序与父节点顺序对应

核心代码

int tail = 1; //tail 指向下一个要入队的节点，1 已经入队了，所以 tail 从 1 开始
for (int head = 0; head < n; head++)
while (node[head]、node[tail] 之间存在边) tail++;
printf("%s", node[0] == 1 && tail == n ? "Yes" : "No");

输入的节点序列但凡有一处不满足 BFS 序列的要求

node[head]、node[tail] 之间就不存在边，tail 就会卡住不动而不能到达 n

理解这点是理解这种思路的关键

细节

注意第一个节点一定要是 1，需要特判

无论节点序列是否是合法的 BFS 序列，都能够保证先入队的节点深度不大于后入队的节点
因为保证了第一个节点一定是 1，后续节点都是从前向后扩展出来的
因此入队时只需要判断两节点之间是否存在边，而不需要判断父子关系

怎么高效地判断两节点之间边的存在性？

邻接矩阵存不下 (200000)^2，要用邻接表，且邻接表中的子数据结构用 set，而不是链表/vector

因为链表/vector 查询特定边的效率较低。set 就比较合适

因为所有边的边权都是相同的，所以不用 map

虽然没有排序的需求，但 set 有时其实更快

实测本题 unordered_set 效率略低于 set，前者优化后约 500ms，后者优化后约 300ms

优化

循环条件可以加上 head < tail，这是队列的性质，队首不能超过队尾
节点序列不是合法的 BFS 序列时，tail 就会卡住不动，导致 head 超过 tail，提前终止循环
为什么不是 <=，因为 tail 在此处的含义和一般队列不同，指向下一位

当然 head <= tail 也不会 WA

代码

#include <set>
#include <cstdio>
using namespace std;
const int N = 200010;
set<int> g[N];
int n, node[N];
int main()
{scanf("%d", &n);for (int i = 1; i < n; i++){int x, y;scanf("%d%d", &x, &y);g[x].insert(y);g[y].insert(x);}for (int i = 0; i < n; i++) scanf("%d", &node[i]);if (node[0] != 1) return puts("No") * 0;int tail = 1;for (int head = 0; head < n && head < tail; head++)while (g[node[head]].count(node[tail])) tail++;return puts(tail == n ? "Yes" : "No") * 0;
}