题解 CF1037D 【Valid BFS?】

小粉兔 · 2018-09-03 19:53:31 · 题解

短码^- \Delta ^-。

思路：输入的a数组确定了每个点遍历到的前后顺序关系，应该优先遍历先出现的点。那么我们按照优先级进行BFS，应该要得到和a数组一样的遍历顺序。

所以通过输入的数组确定每个节点的优先级，一个节点x出现时间越早，它的优先级就越高。定义一个数组b_i表示节点i在a数组中出现的位置。

邻接链表按照优先级排序，这里我用了vector这一支持排序的容器，排序的比较函数我使用了lambda表达式。

接下来从节点1进行BFS，按照优先级的顺序进行遍历，注意判断不能走父亲节点的边。

最后判断BFS序列是否和输入一致即可。

#include<bits/stdc++.h>
using namespace std;
int n,x,y,a[200001],b[200001],A[200001],c;
vector<int> G[200001];
int que[200001],l,r;
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i) scanf("%d%d",&x,&y), G[x].push_back(y), G[y].push_back(x);
    for(int i=1;i<=n;++i) scanf("%d",a+i), b[a[i]]=i;
    for(int i=1;i<=n;++i) sort(G[i].begin(),G[i].end(),[](int x,int y){return b[x]<b[y];});
    que[l=r=1]=1;
    while(l<=r){
        int u=que[l++];
        A[++c]=u;
        for(int i:G[u]) if(b[i]>b[u]) que[++r]=i;
    }
    for(int i=1;i<=n;++i) if(a[i]!=A[i]) return 0*puts("No");
    return 0*puts("Yes");
}