Valid BFS? CodeForces - 1037D（思维 bfs） - JavaScript

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

我真是一只菜狗。。。。。。emm。。。

题意：

判断一个从1开始的队列是否可以按照bfs的顺序进行遍历。。必须从1开始。。。然后后边依次是bfs顺序

解析：

看代码能看懂吧。。。emm。。。就是把每个有关系的用map标记一下

然后bfs的时候加一个循环进队列就好了 emm。。/。

#include <bits/stdc++.h>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define rep(i, a, n) for(int i=a; i<n; i++)

#define lap(i, a, n) for(int i=n; i>=a; i--)

#define lep(i, a, n) for(int i=n; i>a; i--)

#define rd(a) scanf("%d", &a)

#define rlld(a) scanf("%lld", &a)

#define rc(a) scanf("%c", &a)

#define rs(a) scanf("%s", a)

#define pd(a) printf("%d\n", a);

#define plld(a) printf("%lld\n", a);

#define pc(a) printf("%c\n", a);

#define ps(a) printf("%s\n", a);

#define MOD 2018

#define LL long long

#define ULL unsigned long long

using namespace std;

const int maxn = , INF = 0x7fffffff;

int n;

map<int, bool> w[maxn];

int a[maxn];

bool bfs()

{

    queue<int> Q;

    int nex = ;

    if(a[nex] != ) return false;

    Q.push(a[nex]);

    nex++;

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        int v = a[nex];

        while(w[u][v])

        {

            Q.push(v);

            nex++;

            v = a[nex];

        }

    }

    if(nex == n) return true;

    return false;

}

int main()

{

    rd(n);

    int u, v;

    rep(i, , n-)

    {

        rd(u), rd(v);

        w[u][v] = w[v][u] = ;

    }

    rep(i, , n)

        rd(a[i]);

    if(n == ) cout<< "Yes" <<endl;

    else if(bfs()) cout<< "Yes" <<endl;

    else cout<< "No" <<endl;

    return ;

}