题解 | #相遇#

// 有向无环图
#include <bits/stdc++.h> 

using namespace std;

const int mod = 100007;

vector<vector<int>> e;

vector<int> ind; // 节点入度！

vector<int> dfn; // 节点出度！

vector<int> mdfn; // 出度对应的节点！

int main(){
    int cnt = 0;
    int n,m,t;
    cin >> n >> m >> t;
    e.resize(n+1);
    ind.resize(n+1);
    dfn.resize(n+1);
    mdfn.resize(n+1);
    
    
    for(int i = 1; i <= m; i++){
        int u,v;
        cin >> u >> v;
        e[u].push_back(v);
        ++ind[v]; // 入度
    }
    
    queue<int> queue;
    // 拓扑排序！
    for(int i = 1; i <= n; i++) if(!ind[i]) queue.push(i); // 入度为0的节点，即可以作为初始的节点；
    while(!queue.empty()){
        int u = queue.front(); queue.pop();
        dfn[u] = ++cnt; 
        mdfn[cnt] = u; // 排在 cnt 位置上的节点！
        for(auto next : e[u]){
            if(--ind[next] == 0) queue.push(next); // 去掉u所带来的入度后，剩余可以做起点的节点！
        }
    }// 排序结束后，每个节点对应一个位置！
    
    vector<int> dp(n+1); // dp[i] 表示从 i 到t的路径数！
    dp[t] = 1;
    
    for(int i = n; i > 0; i--){ // 从内向外（排序的最后也就是入度最多的那些节点）开始递推
        int u = mdfn[i];
        for(auto next : e[u]){
            dp[u] = (dp[u] + dp[next]) % mod;
        }
    }
    
    int q; 
    cin >> q;
    
    while(q--){
        int u;
        cin >> u;
        cout << dp[u] << endl;
    }
    return 0;
}