Codefest 18 (rated, Div. 1 + Div. 2), problem: (D) Valid BFS? 【模拟bfs】

一百个Chocolate · CSDN · · 2020-01-30 17:16

题意

给出一棵树，再给出一段序列吗，问这段序列是不是这棵树可行的bfs序

思路

直接模拟一遍bfs。

先对构树的邻接表通过序列中的数的次序进行排序，再直接对树bfs，看其结果是否相同即可

code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
int n;
vector<int> G[maxn];
int idx[maxn],a[maxn];
int vis[maxn];
queue<int> q;
bool bfs(){
    q.push(1);
    vis[1]=1;
    int k=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        if(now!=a[k])
            return 0;
        else
            k++;
        for(auto v:G[now]){
            if(v==now) continue;
            if(!vis[v]){
                vis[v]=1;
                q.push(v);
            }
        }
    }
    return 1;
}
bool cmp(int a,int b){
    return idx[a]<idx[b];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        idx[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
        sort(G[i].begin(),G[i].end(),cmp);
    if(bfs())
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}