[Codemarshal] H. The Great Kind King of Tanguzi

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : H. The Great Kind King of Tanguzi
                    BAPS-BUBT NATIONAL PROGRAMMING CAMP, 2016 ONLINE SELECTION CONTEST
Source            : Codemarshal
Category          : Graph Theory, Strongly Connected Components
Algorithm         : SCC
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e5 + 5;  
  
vector < vector <int> > graph;  
vector < vector <int> > rgraph;  
vector < vector <int> > dag;  
  
int finishTime[maxn];  
int dfsTime;  
bool vis[maxn];  
bool vis1[maxn];  
  
void dfs(int u)  
{  
      vis[u] = 1;  
      for (int v : graph[u])  
      {  
            if (vis[v]) continue;  
            dfs(v);  
      }  
      finishTime[u] = ++dfsTime;  
}  
  
int compo;  
int compo_num[maxn];  
int compo_sze[maxn];  
  
void dfs_scc(int u)  
{  
      vis1[u] = 1;  
      compo_num[u] = compo;  
      compo_sze[compo]++;  
      for (int v : rgraph[u])  
      {  
            if (vis1[v]) continue;  
            dfs_scc(v);  
      }  
}  
  
int dp[maxn];  
bool memoize[maxn];  
  
int solve(int u)  
{  
      int &ret = dp[u];  
      bool &mem = memoize[u];  
      if (mem) return ret;  
      mem = 1;  
      int sum = compo_sze[u];  
      for (int v : dag[u]) sum += solve(v);  
      return ret = sum;  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
//      #ifndef ONLINE_JUDGE  
//            freopen("in.txt", "r", stdin);  
//      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int tnode, tedge;  
            cin >> tnode >> tedge;  
            graph.resize(tnode + 1);  
            rgraph.resize(tnode + 1);  
            vector < pair <int, int> > Edge;  
            for (int e = 1; e <= tedge; e++)  
            {  
                  int u, v;  
                  cin >> u >> v;  
                  graph[u].push_back(v);  
                  rgraph[v].push_back(u);  
                  Edge.push_back({u, v});  
            }  
            dfsTime = 0;  
            memset(vis, 0, sizeof vis);  
            for (int i = 1; i <= tnode; i++)  
            {  
                  if (vis[i]) continue;  
                  dfs(i);  
            }  
            vector < pair <int, int> > vec;  
            for (int i = 1; i <= tnode; i++) vec.push_back({finishTime[i], i});  
            sort(vec.begin(), vec.end());  
            reverse(vec.begin(), vec.end());  
            memset(vis1, 0, sizeof vis1);  
            memset(compo_num, 0, sizeof compo_num);  
            memset(compo_sze, 0, sizeof compo_sze);  
            compo = 0;  
            for (int i = 0; i < vec.size(); i++)  
            {  
                  int u = vec[i].second;  
                  if (vis1[u]) continue;  
                  ++compo;  
                  dfs_scc(u);  
            }  
            dag.resize(compo + 1);  
            for (int i = 0; i < tedge; i++)  
            {  
                  int u = compo_num[ Edge[i].first ];  
                  int v = compo_num[ Edge[i].second ];  
                  if (u == v) continue;  
                  dag[u].push_back(v);  
            }  
            memset(memoize, 0, sizeof memoize);  
            for (int i = 1; i <= compo; i++) dp[i] = solve(i);  
            long long ans = 1;  
            for (int i = 1; i <= tnode; i++)  
            {  
                  int sze = dp[ compo_num[i] ];  
                  ans = (1LL * sze * ans) % 1000000007;  
            }  
            cout << "Case " << tcase << ": " << ans << '\n';  
  
            graph.clear();  
            rgraph.clear();  
            dag.clear();  
      }  
}