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");

}

巴特西

cf1037D. Valid BFS?(BFS?)

题意

Sol

最新文章

热门文章