专栏首页数据结构与算法cf1037D. Valid BFS?(BFS?)

cf1037D. Valid BFS?(BFS?)

题意

题目链接

Sol

非常妙的一道题。。

可以这样想,在BFS序中较早出现的一定是先访问的,所以把每个点连出去的边按出现的前后顺序排个序

看一下按顺序遍历出来的序列与给出的是否相同就行了

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], dfn[MAXN], tot, vis[MAXN], tim[MAXN];
vector<int> v[MAXN];
int comp(const int &x, const int &y) {
    return tim[x] < tim[y];
}
void BFS() {
    queue<int> q;
    q.push(1);
    while(!q.empty()) {
        int p = q.front(); q.pop();
        dfn[++tot] = p; vis[p] = 1;
        for(int i = 0, to; i < v[p].size(); i++) {
            if(!vis[(to = v[p][i])]) q.push(to);
        }
    }
}
main() {
    N = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    for(int i = 1; i <= N; i++) tim[a[i] = read()] = i;
    for(int i = 1; i <= N; i++) 
        sort(v[i].begin(), v[i].end(), comp);
    BFS();
    //for(int i = 1; i <= N; i++) printf("%d ", dfn[i]); puts("");
    for(int i = 1; i <= N; i++)
        if(dfn[i] != a[i]) {puts("No"); return 0;}
    puts("Yes");
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P4725 【模板】多项式对数函数(多项式ln)

    可以直接对两边求导\(G'(A(x)) = F'(A(x))A'(x) = \frac{A(x)}{A'(x)}\)

    attack
  • 次小生成树

    次小生成树 次小生成树 我们已经熟知了求最小生成树的方法,用kruskal,prim算法都可以搞 那么我们如何求次小生成树呢? 这里次小生成树的定义是 边...

    attack
  • P3808 【模版】AC自动机(简单版)

    题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

    attack
  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • 洛谷P2312 解方程(暴力)

    对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

    attack
  • 10:Challenge 3(树状数组直接修改)

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

    attack
  • 力扣(LeetCode)刷题,简单+中等题(第30期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • 力扣(LeetCode)刷题,简单题(第27期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • 力扣(LeetCode)刷题,简单+中等题(第26期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • Day2上午解题报告

    预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

    attack

扫码关注云+社区

领取腾讯云代金券