[codeforces 1037D] Valid BFS? 解题报告(验证bfs序,思维题)
2024-10-01 12:12:16
题目链接:http://codeforces.com/problemset/problem/1037/D
题目大意:
给出一棵树,询问一个序列是否可能为这棵树从节点1开始遍历的bfs序
题解:
对于每个节点,令其权值等于该元素在给序列中出现的位置
把每个节点的出边按照到达点的权值排序,来一次bfs得到一个bfs序,判断当前bfs序与给定序列是否相等即可
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std; const int N=2e5+;
int n,m,s;
int vis[N],giv[N],u[N],v[N],pos[N];
struct node
{
int y,val;
};
bool operator < (node x,node y) {return x.val<y.val;}
vector<node> g[N];
vector <int> p;
inline int read()
{
char ch=getchar();
int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
void bfs()
{
queue <int> q;
vis[]=;
q.push();
while (!q.empty())
{
int k=q.front();q.pop();
p.push_back(k);
for (int i=;i<g[k].size();i++)
{
int y=g[k][i].y;
if (vis[y]) continue;
vis[y]=;
q.push(y);
}
}
}
int main()
{
n=read();
for (int i=;i<n;i++)
{
u[i]=read();v[i]=read();
}
for (int i=;i<=n;i++)
{
giv[i]=read();
pos[giv[i]]=i;
}
for (int i=;i<n;i++)
{
g[u[i]].push_back((node){v[i],pos[v[i]]});
g[v[i]].push_back((node){u[i],pos[u[i]]});
}
for (int i=;i<=n;i++) sort(g[i].begin(),g[i].end());
/*for (int i=1;i<=n;i++)
{
for (int j=0;j<g[i].size();j++) printf("%d ",g[i][j].val);
printf("\n");
}*/
bfs();
bool flag=;
for (int i=;i<=n;i++) if (p[i-]!=giv[i]) {flag=;break;}
if (flag) puts("Yes");
else puts("No");
return ;
}
最新文章
- 使用mapreduce计算环比的实例
- Swift 备忘单和快速参考
- 在 Xcode 6 中使用矢量图( iPhone 6 置配 UI)
- 最新微信小程序(应用号)视频教程,实战教程
- ToggleButton
- Java classes and class loading
- DBA常用SQL之数据库基础信息
- ***ECharts图表入门和最佳实践
- Text Template Transformation Toolkit
- HDU 1280 前m大的数
- 【PHP分享】Windows tail工具分享
- HSQL
- mysql之 mysql 5.6不停机主从搭建(一主一从基于GTID复制)
- 防止fixed元素遮挡其他元素的方法
- MYSQL数据库表按月备份,滚动,保留6次备份
- 开源库BaseRecyclerViewAdapterHelper
- idea使用破解版mybatis plugin插件失败,idea打不开的解决方案
- SolrCloud集群配置
- GCD LCM UVA - 11388
- mysqlsh : mysql shell tutorial