Codeforces | CF1037D 【Valid BFS?】

题目大意:给定一个\(n(1\leq n\leq 2\cdot10^5)\)个节点的树的\(n-1\)条边和这棵树的一个\(BFS\)序\(a_1,a_2,\dots,a_n\),判断这个\(BFS\)序是否是一个从节点\(1\)开始的合法\(BFS\)序,若合法则输出\(Yes\),否则输出\(No\)
题目核心问题是判断给出的\(BFS\)序的合法性,根据\(BFS\)的定义,每个节点的所有子节点在加入队列时应当是连续的,且同深度的节点的子节点入队顺序应该整体与父节点入队顺序相同,不妨把每个节点的所有子节点在给定的\(BFS\)序列中的顺序看做连续的区间.
考虑到\(BFS\)序列不合法的原因有以下可能:

• \(a_1\neq 1\)
  
• 存在\(i,j\)满足\(i<j\)且\(dep[a_i]>dep[a_j]\)
  
• 存在\(i,j\)满足\(i\neq j\)且\(a_i=a_j\)
  
• 存在\(i,j\)满足\(i<j\)且\(a_i\)的某个子节点\(u\)与\(a_j\)的某个子节点\(v\)满足在\(BFS\)序中\(u\)在\(v\)之后

处理思路:对于给出的树先跑一边\(BFS\)求每个点的\(dep\)和其子节点在\(a\)序列中的位置区间,按照上述四种情况进行判断.

下面放\(AC\)代码\(\downarrow\downarrow\downarrow\)

#include<cstdio>//CF1037D
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>

using namespace std;

const int N=200010,NN=400020;

struct interval{
    int l,r;
};

int fr[N],edge[NN],nxt[NN],n,dep[N],vis[N],app[N],a[N],fa[N],dy[N];

interval il[N];

queue<int>q;

void bfs(){
    q.push(1);
    dep[1]=1;
    int u;
    while(!q.empty()){
        u=q.front();
        vis[u]=1;
        q.pop();
        int now=fr[u],v;
        while(now){
            v=edge[now];
            if(!vis[v]){
                dep[v]=dep[u]+1;
                fa[v]=u;
                q.push(v);
                il[u].l=min(il[u].l,dy[v]);
                il[u].r=max(il[u].r,dy[v]);
            }
            now=nxt[now];
        }
    }
}

bool check(){
    if(a[1]!=1){
        return false;
    }
    int nowdep;
    for(int i=1;i<=n;i++){
        if(dep[a[i]]<nowdep||app[a[i]]){
            return false;
        }
        else{
            app[a[i]]=1;
            nowdep=dep[a[i]];
        }
    }
    int tr=1;
    for(int i=1;i<=n;i++){
        if(il[a[i]].l==200010){
            continue;
        }
        if(il[a[i]].l>tr){
            tr=il[a[i]].r;
        }
        else{
            return false;
        }
    }
    return true;
}

int main(){
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<=n;i++){
        il[i].l=200010;
        il[i].r=0;
    }
    for(int i=1;i<n;i++){
        int j=i+n;
        scanf("%d%d",&u,&v);
        edge[i]=v;
        nxt[i]=fr[u];
        fr[u]=i;
        edge[j]=u;
        nxt[j]=fr[v];
        fr[v]=j;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        dy[a[i]]=i;
    }
    bfs();
    if(check()){
        printf("Yes\n");
        return 0;
    }
    else{
        printf("No\n");
        return 0;
    }
    return 0;
}