HackerRank: Kingdom Connectivity (Tarjan SCC+DP)

HackerRank: Kingdom Connectivity (Tarjan+DP)
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     20002
#define inf    2000000010
#define MD     1000000000LL
#define eps    1e-9
///===============================///


int n,dp[MX+2],Scp[MX+2];
vector<int>G[MX+2];
vector<int>FG[MX+2];
int tmm=0,St[MX+2],low[MX+2];
int Cp[MX+2],cm,Stk[MX+2],tp;

void Build_DAG( ) {
    for(int i=1; i<=cm; i++)FG[i].clear();
    for(int i=1; i<=n; i++) {
        for(int j=0; j<SZ(G[i]); j++) {
            int v = G[i][j];
            if(Cp[i] == Cp[v])continue;
            FG[ Cp[i] ].pb( Cp[v] );
        }
    }
}

void Tarjan(int u) {
    St[u]=low[u]=++tmm;
    Stk[tp++]=u;
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i];
        if(!St[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        } else if(!Cp[v]) {
            low[u]=min(low[u],St[v]);
        }
    }
    if(St[u]==low[u]) {
        ++cm;
        while(true) {
            int xx=Stk[--tp];
            Cp[ xx ]=cm;/// Comp of xx is cm
            Scp[ cm ]++;
            if( xx==u )break;
        }
    }
}

void Find_SCC( ) {
    CLR(St);
    CLR(Cp);
    CLR(Scp);///Size of every Components
    cm=tmm=tp=0;///tot comp,dfs time & stk ptr
    for(int i=1; i<=n; i++) {
        if(!St[i])Tarjan(i);
    }
    //Build_DAG( );
}

int go(int u) {
    if( u==n ) return 1;
    int &ret=dp[u];
    if(ret!=-1) return ret;
    ret=0;
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i];
        if( Cp[v]==Cp[1] || Cp[v]==Cp[n] || Scp[ Cp[v] ]<=2 )ret=(ret+go(v))%MD;
        ///Means, if next node is in same component as 1 or N then can be traversed easily without infinite loop,
        ///else if the size of other component is less than 2 then, it can also be traverse as it doesn't create loop.
    }
    return ret;
}

int main() {
    int m,x,y;
    S2(n,m);
    fr(i,1,m) {
        S2(x,y);
        G[x].pb(y);
    }
    Find_SCC();
    SET(dp);
    int ans=go(1);
    if(!ans) printf("INFINITE PATHS\n");
    else printf("%d\n",ans);
    return 0;
}