$des$
一个 n 个点 m 条边的无向连通图从 1 号点开始 bfs,可能得到的 bfs 序有很多,
取决于出边的访问顺序。现在给出一个 1 到 n 的排列,判断是否可能是一个 bfs 序。

$sol$
对于每个节点,令其权值为在给定序列中的位置。
然后从 1 号点开始正常的 bfs,出边的访问顺序按照权值从小到大访问。
最后将得到的 bfs 序与给定序列比较,若完全一致则是合法的。

$code$

#include <bits/stdc++.h>

using namespace std;

#define gc getchar()
inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x; } #define LL long long
#define Rep(i, a, b) for(int i = a; i <= b; i ++) const int N = 2e5 + ; int A[N];
int n;
vector <int> V[N];
int W[N];
int B[N], js;
bool use[N];
int ls[N], len; bool Cmp(int a, int b) {
return W[a] < W[b];
} void Bfs(int s) {
queue <int> Q;
use[s] = ;
Q.push(s);
while(!Q.empty()) {
int tp = Q.front();
B[++ js] = tp;
Q.pop();
len = ;
int S = V[tp].size();
Rep(i, , S - ) {
int v = V[tp][i];
if(use[v]) continue;
use[v] = ;
ls[++ len] = v;
}
sort(ls + , ls + len + , Cmp);
Rep(i, , len) Q.push(ls[i]);
}
} int main() {
n = read();
Rep(i, , n - ) {
int u = read(), v = read();
V[u].push_back(v), V[v].push_back(u);
}
Rep(i, , n) A[i] = read();
Rep(i, , n) W[A[i]] = i;
Bfs(); Rep(i, , n) {
if(A[i] != B[i]) {
cout << "No";
return ;
}
}
cout << "Yes"; return ;
}

最新文章

  1. IIS与Apache共用80端口
  2. Linux opencv安装与编译
  3. LNMP安装一键安装包
  4. 关于Java的数据结构HashMap,ArrayList的使用总结及使用场景和原理分析
  5. Linux查找文件
  6. 用pxe启动iso光盘里的pe
  7. 2016030206 - mysql常用命令
  8. Xampp Linux应用
  9. VS2013上利用InstallShield2013LimitedEdition/C#生成安装包
  10. qtp中vb脚本,经典收藏
  11. IOS的KVC
  12. SxsTrace程序追踪 &amp;&amp; 错误信息分析
  13. Swift 笔记汇总
  14. Python爬虫之ip代理池
  15. 心路历程(五)-find work and find house
  16. kmp基础 ekmp
  17. 【亲测有效】Github无法访问或者访问速度的解决方案
  18. findbugs的使用
  19. Item的anchors属性
  20. HashMap、LinkedHashMap、ConcurrentHashMap、ArrayList、LinkedList的底层实现

热门文章

  1. idea单行注释优化成不在行首注释
  2. 一行代码让3D翻转后的文本恢复清晰
  3. CacheManager.Core
  4. keychain不能导出p12证书的解决方法
  5. Ubuntu安装usb库
  6. CentOS7.5 部署Ceph luminous
  7. typescript_类
  8. TCP、UDP、HTTP、HTTPS之间的区别
  9. 编写订单支付api中遇到的问题
  10. Linux主机之间传输文件的几种方法对比