cf 1037D BFS
2024-10-21 14:26:38
$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 ;
}
最新文章
- IIS与Apache共用80端口
- Linux opencv安装与编译
- LNMP安装一键安装包
- 关于Java的数据结构HashMap,ArrayList的使用总结及使用场景和原理分析
- Linux查找文件
- 用pxe启动iso光盘里的pe
- 2016030206 - mysql常用命令
- Xampp Linux应用
- VS2013上利用InstallShield2013LimitedEdition/C#生成安装包
- qtp中vb脚本,经典收藏
- IOS的KVC
- SxsTrace程序追踪 &;&; 错误信息分析
- Swift 笔记汇总
- Python爬虫之ip代理池
- 心路历程(五)-find work and find house
- kmp基础 ekmp
- 【亲测有效】Github无法访问或者访问速度的解决方案
- findbugs的使用
- Item的anchors属性
- HashMap、LinkedHashMap、ConcurrentHashMap、ArrayList、LinkedList的底层实现