#2#9RE求助
查看原帖
#2#9RE求助
477474
wsinb楼主2022/8/13 17:18
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
bool t[N],p[N],book[N],B,a[N][N];
vector<int> r[N],c[N];
int topr[N],topc[N],q[N],step[N],n,m,S,E,L=1,R=1,now;
void find_all_points(int root){
	for(int i=0;i<topr[root];i++){
		int tmp=r[root].at(i);
		if(t[tmp]) continue;
		t[tmp]=true,find_all_points(tmp);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&S,&E);
		if(a[S][E]) continue;
		r[E].push_back(S);c[S].push_back(E);
		topr[E]++,topc[S]++;
		a[S][E]=true;
	}
	scanf("%d%d",&S,&E);
	//读入
	if(S==E){cout<<0;return 0;}
	//特判
	find_all_points(E),t[E]=true;
	if(!t[S]){cout<<-1;return 0;}
	//特判	
	for(int i=1;i<=n;i++){
		B=true;
		for(int j=0;j<topc[i];j++){
			if(!t[c[i].at(j)]){B=false;break;}
		}
		if(topc[i]||i==E) p[i]=B;
	}
	//确认哪些点可以走
	if(!p[S]){cout<<-1;return 0;}
	//特判
	q[R++]=S,book[S]=true,now=S,B=false;
	while(L<R){
		now=q[L];
		for(int i=0;i<topc[now];i++){
			int tmp=c[now].at(i);
			if(p[tmp]&&!book[tmp]) q[R]=tmp,step[R]=step[L]+1,book[tmp]=1;
			if(q[R++]==E){B=true;break;}
		}
		if(B) break;
		L++;
	}
	cout<<step[--R];
	return 0;
}
2022/8/13 17:18
加载中...