从起点出发的所有路径都必须可以到达终点

考虑从终点开始反向拓扑序

class Solution {
public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>>g(n);
        vector<int>d(n,0);
        for(auto&e:edges){
            int a=e[0],b=e[1];
            g[b].push_back(a);
            d[a]++;
        }
        if(d[destination])return false;
        queue<int>q;
        q.push(destination);
        while(q.size()){
            int t=q.front();
            if(t==source)return true;
            q.pop();
            for(auto &ne:g[t]){
                if(--d[ne]==0){
                    q.push(ne);
                }
            }
        }
        return false;
    }
};

有向图从v出发到达编号最大的点

（可以是本身）

#include<iostream>
#include <vector>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e5 + 10, M = N;
int h[N], e[M], w[N], ne[M], idx;
bool st[N];
int n, m;
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u,int d) {
   if(w[u])return;
   w[u]=d;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j,d);
    }
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(b,a);
    }
    for (int i = n; i >=1; i--) 
        dfs(i,i);
    for(int i=1;i<=n;i++)cout<<w[i]<<" ";
    return 0;
}