寻找道路

思路

• 建两个图, 一个图是原图，一个图是将原图的边全部反向后的图，在反向图中以终点ed为起点进行bfs遍历，标记所有遍历到的点state[i]=true
• 在原图上进行$bfsbfs$遍历，在原本bfs将点加入队列的条件的基础上，增加一个条件：如果一个点$jj$的所有邻接点的$statestate$均为$truetrue$, 才将点$jj$加入队列

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e4 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int h1[N], e1[M], ne1[M], idx1;
int state[N], dis[N]; // state[i]=true代表点i可以到达终点
int start, ed;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    // w[idx] = c;
    h[a] = idx++;
}

void add1(int a, int b)
{
    e1[idx1] = b;
    ne1[idx1] = h1[a];
    h1[a] = idx1++;
}

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    memset(dis, -1, sizeof dis);
    dis[s] = 0;

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        state[t] = true;

        for (int i = h1[t]; i != -1; i = ne1[i])
        {
            int j = e1[i];

            if (dis[j] == -1)
            {
                dis[j] = dis[t] + 1;
                q.push(j);
            }
        }
    }
}

int bfs1(int s)
{
    memset(dis, -1, sizeof dis);
    dis[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty())
    {
        int t = q.front();
        q.pop();

        
        // for (int i = h[t]; i != -1; i = ne[i])
        // {
        //     int j = e[i];
        //     if (state[j] == false)
        //     {
        //         flag = false;
        //         break;
        //     }
        // }
        // if (flag == false)
        //     continue;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dis[j] == -1)
            {
                dis[j] = dis[t] + 1;
                bool flag = true;
                for (int k = h[j]; k != -1; k = ne[k])
                {
                    int kk = e[k];
                    if (state[kk] ==false)
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    q.push(j);
                if (j == ed)
                    return dis[ed];
            }
        }
    }

    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int x, y;
    memset(h, -1, sizeof h);
    memset(h1, -1, sizeof h1);
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        add(x, y);
        add1(y, x);
    }
    cin >> start >> ed;

    bfs(ed);

    cout << bfs1(start) << '\n';

    return 0;
}