题解 | 旺仔哥哥走迷宫

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;

struct Edge{
	int u,v;
	int next;
}edge[N*2];

int n,m,t[N],cnt,head[N];
bool f_res=false;
bool vis[N];

void add(int u,int v){
	edge[++cnt].next=head[u];
	edge[cnt].u=u;
	edge[cnt].v=v;
	head[u]=cnt;
	return;
}


void dfs(int x){
	if(x==n){
		f_res=true;
		return;
	}
	for(int i=head[x];i!=0;i=edge[i].next){
		int to=edge[i].v;
		if(t[to]==1||vis[to]==true) continue;
		vis[to]=true;
		dfs(to);
	}
}


void solve(){
	memset(vis,false,sizeof(vis));
	
	if(t[1]==1||t[n]==1) f_res=false;
	else dfs(1);
	if(f_res==true){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>t[i];
	}
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	
	solve();

    return 0;
}