P2296 [NOIP2014 提高组] 寻找道路,悬关,求改QWQ
查看原帖
P2296 [NOIP2014 提高组] 寻找道路,悬关,求改QWQ
921450
Szy0720楼主2023/8/26 10:05
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10; 
int n,m;
vector<int> G[N],g[N];
bool vis[N],flag[N];
int s,t,step[N];
void bfs1(){
	queue<int>que;
	flag[t]=1;
	que.push(t);
	while(que.size()){
		int x=que.front();
		que.pop();
		for(int i=0;i<G[x].size();i++){
			int y=G[x][i];
			if(flag[y])continue;
			flag[y]=1;
			que.push(y);
		}
	}
}
bool check(int x){
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i];
		if(flag[y]==1)return false;
	}
	return true;
}
int bfs2(){
	queue<int>que;
	que.push(s);
	vis[s]=1;
	step[s]=0;
	while(que.size()){
		int x=que.front();
		for(int i=0;i<=g[x].size();i++){
			int y=g[x][i];
			if(vis[y])continue;
			if(check(y)){
				vis[y]=1;
				step[y]=step[x]+1;
				if(y==t)return step[y];
				que.push(y);
			}
		}
	}
	return -1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		G[y].push_back(x);
	}
	cin>>s>>t;
	bfs1();
	cout<<bfs2()<<endl;
	return 0;
}
2023/8/26 10:05
加载中...