思路与算法

反向BFS先求原图可达终点的点，再一次性排除有出边指向不可达点的顶点；在剩余点诱导图正向BFS求最短路。

正确性说明

题目条件中的可达指原图可达终点，反向遍历恰求此集合。某点所有出边目标在该集合当且仅当该点可出现在答案路径上。删掉不合格点后，余图任一路径满足条件，BFS因边权1求最短。

复杂度

O(n+m)时间、O(n+m)空间，含正反邻接表与两次遍历初始化。

易错点

不要在删点后反复传播失效，可达集合只按原图计算；重边、自环都可能存在，终点没有出边。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n), rev(n);
    while (m--) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].push_back(b);
        rev[b].push_back(a);
    }
    int s, t;
    cin >> s >> t;
    --s;
    --t;
    vector<int> reach(n), good(n, 1), q(1, t);
    reach[t] = 1;
    for (int i = 0; i < (int)q.size(); i++)
        for (int v : rev[q[i]])
            if (!reach[v]) {
                reach[v] = 1;
                q.push_back(v);
            }
    for (int i = 0; i < n; i++) {
        good[i] = reach[i];
        for (int v : g[i])
            if (!reach[v])
                good[i] = 0;
    }
    if (!good[s]) {
        cout << -1 << "\n";
        return 0;
    }
    vector<int> d(n, -1);
    d[s] = 0;
    q.assign(1, s);
    for (int i = 0; i < (int)q.size(); i++)
        for (int v : g[q[i]])
            if (good[v] && d[v] < 0) {
                d[v] = d[q[i]] + 1;
                q.push_back(v);
            }
    cout << d[t] << "\n";
}