题目：https://www.luogu.org/problemnew/show/P2296
先从终点dfs一下能走到终点的，然后从起点bfs即可。O(n+m)。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e4+5,M=2e5+5; int n,m,hd[N],xnt,to[M],nxt[M],st,en,thd[N],tnt,tto[M],txt[M]; int q[N],he,tl,dis[N],k; bool vis[N],flag,fw[N]; int rdn() { int ret=0,fx=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') fx=-1; ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return ret*fx; } void add(int x,int y) { to[++xnt]=y; nxt[xnt]=hd[x]; hd[x]=xnt; } void adt(int x,int y) { tto[++tnt]=y; txt[tnt]=thd[x]; thd[x]=tnt; } void dfs(int cr) { vis[cr]=1; for(int i=thd[cr],v;i;i=txt[i]) if(!vis[tto[i]]) dfs(tto[i]); } int main() { n=rdn(); m=rdn(); for(int i=1,x,y;i<=m;i++) { x=rdn(); y=rdn(); add(x,y); adt(y,x); } st=rdn(); en=rdn(); dfs(en); if(!vis[st])flag=1; for(int i=hd[st];i;i=nxt[i]) if(!vis[to[i]]){flag=1;break;} if(flag){puts("-1");return 0;} q[tl=1]=st; fw[st]=1; while(he<=tl) { k=q[++he]; for(int i=hd[k],v;i;i=nxt[i]) if(vis[v=to[i]]&&!fw[v]) { flag=0; fw[v]=1; for(int j=hd[v];j;j=nxt[j]) if(!vis[to[j]]){flag=1;break;} if(!flag) { dis[v]=dis[k]+1; q[++tl]=v; if(v==en){printf("%d ",dis[v]);return 0;} } } } puts("-1"); return 0; }