1037D - Valid BFS?（思维BFS）

75 阅读 0 评论 50 点赞

我是靠谱客的博主隐形高跟鞋，最近开发中收集的这篇文章主要介绍1037D - Valid BFS?（思维BFS），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

有点意思

题意：给了一颗n节点，n-1条边的树，进行BFS遍历，问遍历顺序是否可能是所给数组的顺序

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

按照进队列的顺序排了一个序，这样就可以我们保证自己写的BFS序最可能是符合所给顺序的BFS序了。如果这样都不行，哪一定不行。感性理解感性理解。

vector建图

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1.5e6+5;
const int MAXM = 1.5e6+5;
typedef long long ll;
std::vector<int> v[MAXM];
//int sum[MAXM];
std::vector<int> G[MAXM];
int arr[MAXM],id[MAXM];
bool vis[MAXM];

bool cmp(int s1, int s2){
    return id[s1] < id[s2] ;
}

bool bfs(){
    vis[1] = 1;
    int cnt = 1;
    queue<int> q ;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(u != arr[cnt]) return 0;
        else cnt++;
        for(int i = 0 ; i < G[u].size(); i ++){
            if(!vis[G[u][i]]){
                vis[G[u][i]]  = 1;
                q.push(G[u][i]);
            }
        }
    }


    return 1;
}


int main(){
    int  n ;
    cin >> n ;
    for(int i = 1; i < n ; 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 >> arr[i];
        id[arr[i]] = i;
    }
    for(int i  = 1 ;i <= n ; i ++) {
        sort(G[i].begin(), G[i].end(),cmp);
    }
    if(bfs()) puts("Yes");
    else puts("No");

    return 0;
}