KFSTB

Problem Link

#include <iostream>

#include <queue>

#include <vector>

#include <stack>

#include <cstdio>

using namespace std;

const int MOD = 1000000007;

bool visited[10001];

stack<int> st;

//get topological sorting of DAG

void dfs(int s, vector<int> graph[])

{

visited[s] = true;

for(int i = 0; i < graph[s].size(); i++)

{

if(!visited[graph[s][i]])

{

dfs(graph[s][i], graph);

}

}

st.push(s);

}

int main()

{

int d, c, b, s, t, x, y;

scanf("%d", &d);

while(d--)

{

scanf("%d%d%d%d", &c,&b,&s,&t);

vector<int> graph[c + 1];

long dp[c + 1];

while(!st.empty())

{

st.pop();

}

for(int i = 0; i < c + 1; i++)

{

visited[i] = false;

dp[i] = 0;

}

dp[s] = 1;

for(int i = 0; i < b; i++)

{

scanf("%d%d",&x,&y);

graph[x].push_back(y);

}

dfs(s, graph);

while(!st.empty())

{

int v = st.top();

st.pop();

for(int i = 0; i < graph[v].size(); i++)

{

dp[graph[v][i]] += dp[v];

dp[graph[v][i]] %= MOD;

}

}

//if source and destination is same increase count

if(s == t)

{

dp[t]++;

}

printf("%ld\n", dp[t]);

}

}