求助
  • 板块CF1037D Valid BFS?
  • 楼主_5555_
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/18 09:41
  • 上次更新2023/10/27 19:46:47
查看原帖
求助
722330
_5555_楼主2022/7/18 09:41

为何 #3 RE

#include<bits/stdc++.h>
#define N 200010

using namespace std;

typedef long long ll;

int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
	{
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
	{
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}

int n,a[N],z[N],k=0,f[N],t[N];
vector <int> v[N];

bool cmp(int x,int y)
{
	return t[x]<t[y];
}

void bfs()
{
	queue <int> q;
	q.push(1);
	while(!q.empty())
	{
		int p = q.front();
		q.pop();
		z[++k] = p,f[p] = 1;
		int l,x=v[k].size();
		for(int i=0;i<x;i++)
			if(!f[(l=v[p][i])]) q.push(l);
	}
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		v[x].push_back(y); v[y].push_back(x);
	}
	for(int i=1;i<=n;i++) 
	{
		a[i]=read();
		t[a[i]] = i;
	}
	for(int i=1;i<=n;i++) 
		sort(v[i].begin(),v[i].end(),cmp);
	bfs();
	for(int i=1;i<=n;i++)
		if(z[i]!=a[i]) 
		{
			printf("No\n");
			return 0;
		}
	printf("Yes\n");
}
2022/7/18 09:41
加载中...