题目描述
提交记录
I. BFS?
Problem ID: 15654
Contest ID: 5942
必做题
Time Limit Exceeded
60 分
题目描述
用BFS算法可以遍历得到一棵树，但是根据遍历结点顺序的不同，最终得到的序列也不同。
在这个问题中，给你一个序列和一棵根结点为1的树，你需要判断通过BFS遍历得到的序列是否和所给序列相同。
输入示例
第一行输入一个整数n(1≤n≤2∗105)，表示树的点数。
接下来n−1行，每行输入两个整数x和y(1≤x,y≤n)，表示一条边。数据保证所给的图是一棵树。
最后一行包含了n个整数a1,a2,…,an(1≤ai≤n)，表示需要判断的序列。
输出示例
如果能通过BFS得到所给的序列，输出"Yes"，否则输出"No"。
样例1
输入样例
4 1 2 1 3 2 4 1 3 2 4
输出样例
Yes
样例2
输入样例
4 1 2 1 3 2 4 1 2 4 3
输出样例
No
样例说明
两个样例所给的树是相同的，这颗树可以得到两种不同的BFS序列：
- 1,2,3,4
- 1,3,2,4
样例2的1,2,4,3并不能与上述BFS序列相匹配。
#include <bits/stdc++.h>
using namespace std;
vector<int>a[200005];
int cnt[200005];
int ans[200005];
int k = 1;
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i<=n-1;i++)
{
int x,y;
scanf("%d %d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(int i = 1;i<=n;i++)
{
scanf("%d",&cnt[i]);
}
ans[1] = cnt[1];
int x = 1;
while(x<n)
{
int q = k;
for(int i = x+1;i<=x+a[x].size()&&i<=n;i++)
{
bool flag = 0;
for(int j = 1;j<=k;j++)
{
if(find(a[ans[j]].begin(),a[ans[j]].end(),cnt[i])!=a[ans[j]].end())
{
flag = 1;
break;
}
}
if(flag == 0)
{
printf("No");
return 0;
}
ans[++k] = cnt[i];
}
ans[q] = 0;
x = x+a[x].size();
}
printf("Yes");
return 0;
}
代码TLE60分
