题目链接: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 ;
}

最新文章

  1. 使用mapreduce计算环比的实例
  2. Swift 备忘单和快速参考
  3. 在 Xcode 6 中使用矢量图( iPhone 6 置配 UI)
  4. 最新微信小程序(应用号)视频教程,实战教程
  5. ToggleButton
  6. Java classes and class loading
  7. DBA常用SQL之数据库基础信息
  8. ***ECharts图表入门和最佳实践
  9. Text Template Transformation Toolkit
  10. HDU 1280 前m大的数
  11. 【PHP分享】Windows tail工具分享
  12. HSQL
  13. mysql之 mysql 5.6不停机主从搭建(一主一从基于GTID复制)
  14. 防止fixed元素遮挡其他元素的方法
  15. MYSQL数据库表按月备份,滚动,保留6次备份
  16. 开源库BaseRecyclerViewAdapterHelper
  17. idea使用破解版mybatis plugin插件失败,idea打不开的解决方案
  18. SolrCloud集群配置
  19. GCD LCM UVA - 11388
  20. mysqlsh : mysql shell tutorial

热门文章

  1. bzoj1503: [NOI2004]郁闷的出纳员(伸展树)
  2. 超高性能管线式HTTP请求(实践&#183;原理&#183;实现)
  3. caffe遇到的错误记录
  4. SQL Server 获取两个日期间的日期
  5. Oracle学习系类篇(一)
  6. B/S发布到服务器
  7. tp5页面跳转,空控制器空方法
  8. Android Finalizing a Cursor that has not been deactivated or closed
  9. 安装Oracle 12c及解决遇到的问题
  10. Pyhton学习——Day27