在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。

注意：图G中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。

第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。
接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。

输出文件名为road.out。
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。

road.in	road.out
3 2 1 2 2 1 1 3	－1

road.in	road.out
6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5	3

对于30%的数据，0< n ≤10，0< m ≤20；
对于60%的数据，0< n ≤100，0< m ≤2000；
对于100%的数据，0< n ≤10,000，0< m ≤200,000，0< x,y,s,t≤n，x≠t。

解析->

这道题一开始做的时候完全没有头绪，后来想到了用并查集维护，然后死的很惨……后来发现可以反向建图，然后标记从终点能走到的点，在正着跑spfa（其实也可以bfs），在枚举点时，判断这个点的出边有没有连接反向建图时没有被标记的点（即走不到终点的点），如果有，则不走这个点。
最后就可以求出答案了。如果答案很大时，则为不能走到，输出-1。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int first[23333], next[500000], d[23333], tot = 0, bj[233333];
bool used[23333], could[23333], t[23333];
struct qer
{
	int from, to;
}es[500000];
queue <int> q;
//-------------------------------------------
int firstf[23333], nextf[500000], totf = 0;
bool usedf[23333];
struct qerf
{
	int from, to;
}esf[500000];
void buildf(int f, int t)
{
	esf[++totf] = (qerf){f, t};
	nextf[totf] = firstf[f];
	firstf[f] = totf;
}
//-----------------------------------------------
void build(int f, int t)
{
	es[++tot] = (qer){f, t};
	next[tot] = first[f];
	first[f] = tot;
}
void findcan(int s)
{
	could[s] = 1;
	t[s] = 1;
	for(int i = firstf[s]; i != -1; i = nextf[i])
	{
		int v = esf[i].to;
		if(!t[v])
			findcan(v);
	}
}
bool cankill(int x)
{
	for(int i = first[x]; i != -1; i = next[i])
	{
		int v = es[i].to;
		if(!could[v])
			return true;
	}
	return false;
}
void spfa(int s)
{
	d[s] = 0;
	used[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		used[u] = 0;
		if(cankill(u))
			continue;
		for(int i = first[u];i != -1;i = next[i])
		{
			int v = es[i].to;
			if(d[v] > d[u] + 1)
			{
				d[v] = d[u] + 1;
				if(used[v] == 0)
				{
					used[v] = 1;
					q.push(v);
				}
			}
		}
	}
}
/*---------------------------------------*/
int main()
{
	memset(first, -1, sizeof(first));
	memset(d, 0x3f, sizeof(d));
	memset(firstf, -1, sizeof(firstf));
	int n, m, st, et;
	cin>>n>>m;
	for(int i = 1;i <= m;i ++)
	{
		int f, t;
		scanf("%d%d", &f, &t);
		build(f, t);
		buildf(t, f);
	}
	scanf("%d%d", &st, &et);
	findcan(et);
	spfa(st);
	if(d[et] > 0x7fff)
		cout<<-1;
	else
		cout<<d[et];
	return 0;
}

最后附上我连跪截图