D. Valid BFS?

题目链接:https://codeforces.ml/problemset/problem/1037/D

题意:给定一棵树 和一个bfs序列 问以1为根用bfs开始遍历能否得到这个序列

思路:考虑将相邻的边 按照先后排序后 跑一遍bfs 看是否能对的上,全部对的上即为合法序列

![]()![]()```
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=2e5+10;
4 const int mod=1e9+7;
5 #define ll long long
6 #define pi pair<int,int>
7 #define fi first
8 #define sc second
9 #define pb push_back
10 vector<int>E[maxn];
11 int p[maxn];
12 bool cmp(int a,int b)
13 {
14 return p[a]<p[b];
15 }
16 int a[maxn],vis[maxn];
17
18
19 int main()
20 {
21 ios::sync_with_stdio(0);
22 cin.tie(0);
23 int n;
24 cin>>n;
25 for(int i=1;i<n;i++)
26 {
27 int x,y;
28 cin>>x>>y;
29 E[x].pb(y);
30 E[y].pb(x);
31 }
32 for(int i=1;i<=n;i++) cin>>a[i],p[a[i]]=i;
33 for(int i=1;i<=n;i++) sort(E[i].begin(),E[i].end(),cmp);
34 queue<int>q;
35 q.push(1);
36 vis[1]=1;
37 int tot=0;
38 while(!q.empty())
39 {
40 int u=q.front();
41 q.pop();
42 if(u!=a[++tot])
43 {
44 cout<<"NO"<<'\n';
45 return 0;
46 }
47 for(auto &v:E[u])
48 {
49 if(vis[v]) continue;
50 vis[v]=1;
51 q.push(v);
52 }
53 }
54 cout<<"YES"<<'\n';
55
56
57
58
59
60 }



View Code

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。