题解 | #寻找道路#

很有意思的一道题，这道题题目要求“路径上的所有点的出边所指向的点都直接或间接与终点连通”，怎么判断是否能到达重点呢，可以反向建边，没有访问到的点一定就是不与终点连接的点，然后将该点的所有临界点标记为false，意思是，该点的临接点不可直接或间接到达终点，再次bfs的时候就不需要再访问

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
	int u,v;
	node(int a,int b){
		u=a; v=b;
	}
	node(){
	}
};
const int N=1e4+5;
int vis[N];
int s,t;
const int M=2e5+5;
int step[N];
vector<node> ve[M];
queue<int> q;
int back[N];
void bfs(){
	while(!q.empty()){
		int tmp=q.front();
		q.pop();
		for(int i=0;i<ve[tmp].size();i++){
			int v=ve[tmp][i].v;
			if(!vis[v]){
			//	step[v]=step[tmp]+1;
				vis[v]=1;
				q.push(v);
			}
		}
	}
}

void bfsen(){
	while(!q.empty()){
		int tmp=q.front();
		q.pop();
		for(int i=0;i<ve[tmp].size();i++){
			int v=ve[tmp][i].v;
			if(back[v]){
				back[v]=0;
				step[v]=step[tmp]+1;
				q.push(v);
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		ve[y].push_back(node(y,x));
	}
	
	cin>>s>>t;
	vis[t]=1;
	q.push(t);
	bfs();
	memcpy(back,vis,sizeof(vis));
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			for(int j=0;j<ve[i].size();j++){
				int v=ve[i][j].v;
				if(back[v]){
					back[v]=0;
				}
			}
		}
	}
	queue<int> p;
	q=p;
	q.push(t);
	back[s]=1;
	bfsen();
	if(step[s])	cout<<step[s]<<endl;
	else	cout<<"-1"<<endl;
	return 0;
}