[Spoj] KFSTB - Help the Commander in Chief

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : KFSTB - Help the Commander in Chief
Source            : Spoj 
Category          : Graph Theory, Dynamic Programing
Algorithm         : DAG, DP
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll          long long
#define mod         1000000007
#define sz(a)       (int)a.size()
#define memo(a, b)   memset(a, b, sizeof a)
 
static const int maxn = 1e4 + 5;
 
inline int read()    { int a; scanf("%d", &a); return a; }
 
vector <int> dag[maxn];
int tnode, tedge;
int src, des;
 
ll dp[maxn];
bool mem[maxn];
 
inline ll countPath(int u)
{
      if (u == des) return 1;
      if (sz(dag[u]) == 0) return 0;
      ll &ret = dp[u];
      bool &mm = mem[u];
      if (mm) return ret;
      mm = 1;
      ret = 0;
      for (int v : dag[u]) ret = (ret + countPath(v)) % mod;
      return ret;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      int tc = read();
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            tnode = read();
            tedge = read();
            src = read();
            des = read();
            for (int e = 1; e <= tedge; e++)
            {
                  int u = read();
                  int v = read();
                  dag[u].emplace_back(v);
            }
            memo(mem, 0);
            ll tpath = countPath(src);
            printf("%lld\n", tpath);
            for (int i = 0; i < maxn; i++) dag[i].clear();
      }
}