Codeforces 1037D(BFS序)

Codeforces 1037D
题意:给出一棵树以及一个序列,问这个序列是否可能是原树的 BFS 序。
考虑 BFS 分层,然后每次读进来数判断一下是否能接上。看代码即可。
注意 BFS 序要按顺序,比如上一层在前面入队的是1,那么遍历这一层时一定是1的所有孩子在前面

本题结合了 BFS 序,对于 BFS 不一定要用队列,可以边处理边 BFS 一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 200000 + 5, ZINF = 1000000000;
int n, bfn[MAXN], vis[MAXN], sz;
std::vector<int > G[MAXN];
std::multiset<int > s;
void clean() {
sz = 0, ms(bfn, 0), ms(vis, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i < n; i++) scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x);
vis[1] = 1, s.insert(0);
for (int a, i = 1; i <= n; i++) {
scanf("%d", &a);
if (!vis[a]) return printf("No\n"), 0;
if (bfn[a] != *s.begin()) return printf("No\n"), 0;
sz++;
for (int i = 0; i < (int)G[a].size(); i++) {
int v = G[a][i];
if (!vis[v]) vis[v] = 1, bfn[v] = sz, s.insert(sz);
}
s.erase(s.find(bfn[a]));
}
printf("Yes\n");
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
------ 本文结束 ------