思路:求出可联通到终点的点,再分别求出所有出去的路线都可以到达的和有些出去的路线不能达到的,然后BFS找出一条所有点都能到达的路线,代码:
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector <int> a[10010]{};
int st,ed;
int c[10010]{};
bool d[10010]{};
void dfs(int x,int h[]){
if(x==ed){
for(int i=1;i<=h[0];i++){
c[h[i]]=1;
}
return;
}
for(auto y:a[x]){
if(!d[y]){
d[y]=1;
h[++h[0]]=y;
dfs(y,h);
h[0]--;
}
else{
if(c[y]){
c[x]=1;
}
}
}
return;
}
void dfs2(int x){
if(d[x]||c[x]==0||x==ed){
return;
}
d[x]=1;
for(auto y:a[x]){
dfs2(y);
if(!c[y]){
c[x]=2;
break;
}
}
return;
}
struct aaa{
int a,b;
};
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
}
scanf("%d%d",&st,&ed);
for(int i=1;i<=n;i++){
d[i]=1;
int h[10010]{};
h[++h[0]]=i;
dfs(i,h);
}
memset(d,0,sizeof(d));
dfs2(st);
if(c[st]==1){
queue <aaa> f;
f.push({st,0});
memset(d,0,sizeof(d));
d[st]=1;
int ans=1000000000;
while(!f.empty()){
if(f.front().a==ed){
ans=min(ans,f.front().b);
}
else for(auto y:a[f.front().a]){
if(!d[y]&&c[y]==1){
d[y]=1;
f.push({y,f.front().b+1});
}
}
f.pop();
}
printf("%d",ans);
}
else{
printf("-1");
}
return 0;
}