Description
在有向图 G 中，每条边的长度均为 1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
路径上的所有点的出边所指向的点都直接或间接与终点连通。
在满足条件 1 的情况下使路径最短。
注意：图 G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
Input
第一行有两个用一个空格隔开的整数 n 和 m ，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x,y，之间用一个空格隔开，表示有一条边从点 x 指向点 y 。
最后一行有两个用一个空格隔开的整数 s,t，表示起点为 s，终点为 t 。
Output
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出 −1 。
Sample Input1
3 2
1 2
2 1
1 3
Sample Output1
-1
Sample Input2
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
Sample Output2
3
Hint
解释1：
如上图所示，箭头表示有向道路，圆点表示城市。起点 1 与终点 3 不连通，所以满足题目描述的路径不存在，故输出 −1 。
解释2：
如上图所示，满足条件的路径为 1 – > 3 – > 4 – > 5 。注意点 2 不能在答案路径中，因为点 2 连了一条边到点 6 ，而点 6 不与终点 5 连通。
【数据范围】
对于 30% 的数据， 0 < n ≤ 100， 0 < m ≤ 200 ;
对于 60% 的数据， 0 < n ≤ 1000， 0 < m ≤ 20000 ;
对于 100% 的数据，0 < n ≤ 10000 , 0 < m ≤ 200000 , 0 < x , y , s , t ≤ n , x , s ≠ t 。
题解
反向建图，从T开始dfs 对于能到达的点打标记。
for循环每个点，若没有标记则把其通向的点一起删掉。
最后跑SPFA 输出dis [S]。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct emm{
int e,f;
}a[200007];
int h[10007];
int tot=0;
void con(int x,int y)
{
a[++tot].f=h[x];
h[x]=tot;
a[tot].e=y;
return;
}
bool ss[10007];
bool sf[10007];
void dfs(int x)
{
for(int i=h[x];i;i=a[i].f)
if(!ss[a[i].e])
{
ss[a[i].e]=1;
dfs(a[i].e);
}
return;
}
int q[5000007];
int dis[10007];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
con(y,x);
}
int s,t;
scanf("%d%d",&s,&t);
ss[t]=1;
dfs(t);
for(int i=1;i<=n;++i)
if(!ss[i])
{
sf[i]=1;
for(int j=h[i];j;j=a[j].f)
sf[a[j].e]=1;
}
memset(dis,127,sizeof(dis));
int he=0,ta=1;
q[1]=t;
dis[t]=0;
do
{
he++;
int x=q[he];
for(int i=h[x];i;i=a[i].f)
if(!sf[a[i].e])
{
sf[a[i].e]=1;
dis[a[i].e]=dis[x]+1;
q[++ta]=a[i].e;
}
}while(he<ta);
if(dis[s]<10007)cout<<dis[s];
else cout<<-1;
return 0;
}
