[CodeChef] GRAPHCNT - Counting on a directed graph

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : GRAPHCNT - Counting on a directed graph
Source            : CodeChef
Category          : Graph Theory
Algorithm         : Dominator Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define vi        vector <int>  
#define eb        emplace_back  
#define sz(v)     (int)v.size()  
#define ll        long long int  
  
static const int maxn = 2e5 + 5;  
  
vi graph[maxn],    // Input Graph.  
   rgraph[maxn],   // Reverse Graph.  
   Tree[maxn],     // Final Dominator Tree.  
   bucket[maxn];   // For a vertex i, it stores a list of vertices for which i is the  
                   // semi-dominator. Initially it is empty.  
  
int arr[maxn],     // Mapping of i'th node to its new index, equal to the arrival time  
                   // of node in dfs tree.  
    par[maxn],     // Parent of node i in dfs tree.  
    rev[maxn],     // Reverse mapping of i'th node to the original label in input graph.  
    sdom[maxn],    // Label of semi-dominator of i'th node. Initially sdom[i] = i.  
    dom[maxn],     // Label of immediate-dominator of the i'th node. Initially dom[i] = i.  
    dsu[maxn],     // Parent of i'th node in the forest maintained during step 2 of the  
                   // algorithm. Initially dsu[i] = i.  
    label[maxn],   // At any point of time, label[i] stores the vertex v with minimum sdom,  
                   // lying on path from i to the root of the (dsu) tree in which node i  
                   // lies. Initially, label[i] = i.  
    dfsTime;  
  
// 1 - Based directed graph input.  
  
int Find(int u, int x = 0)  
{  
      if (u == dsu[u]) return x ? -1 : u;  
      int v = Find(dsu[u], x+1);  
      if (v < 0) return u;  
      if (sdom[ label[ dsu[u] ] ] < sdom[ label[u] ])  
      {  
            label[u] = label[ dsu[u] ];  
      }  
      dsu[u] = v;  
      return x ? v : label[u];  
}  
  
void Union(int u, int v)  // Add an edge to u -> v  
{  
      dsu[v] = u;  
}  
  
void dfs(int u)  
{  
      ++dfsTime;  
      arr[u] = dfsTime;  
      rev[dfsTime] = u;  
      label[dfsTime] = dfsTime;  
      sdom[dfsTime] = dfsTime;  
      dsu[dfsTime] = dfsTime;  
      for (int v : graph[u])  
      {  
            if (!arr[v])  
            {  
                  dfs(v);  
                  par[ arr[v] ] = arr[u];  
            }  
            rgraph[ arr[v] ].eb(arr[u]);  
      }  
}  
  
void DominatorTree(int src)  
{  
      dfs(src);  
      int n = dfsTime;  
      for (int i = n; i >= 1; i--)  
      {  
            for (int j = 0; j < sz(rgraph[i]); j++)  
            {  
                  sdom[i] = min(sdom[i], sdom[ Find(rgraph[i][j]) ]);  
            }  
            if (i > 1) bucket[ sdom[i] ].eb(i);  
            for (int j = 0; j < sz(bucket[i]); j++)  
            {  
                  int w = bucket[i][j];  
                  int v = Find(w);  
                  if (sdom[v] == sdom[w]) dom[w] = sdom[w];  
                  else dom[w] = v;  
            }  
            if (i > 1) Union(par[i], i);  
      }  
      for (int i = 2; i <= n; i++)  
      {  
            if (dom[i] != sdom[i]) dom[i] = dom[ dom[i] ];  
            Tree[ rev[i] ].eb(rev[ dom[i] ]);  
            Tree[ rev[ dom[i] ] ].eb(rev[i]);  
      }  
}  
  
int subtreeSize[maxn];  
  
void dfs1(int u, int p = -1)  
{  
      subtreeSize[u] = 1;  
      for (int v : Tree[u])  
      {  
            if (v == p) continue;    
            dfs1(v, u);  
            subtreeSize[u] += subtreeSize[v];  
      }  
}  
  
int main()  
{  
      ///freopen("in.txt", "r", stdin);  
      int tnode, tedge;  
      cin >> tnode >> tedge;  
      for (int e = 1; e <= tedge; e++)  
      {  
            int u, v;  
            cin >> u >> v;  
            graph[u].eb(v);  
      }  
      int src = 1;  
      DominatorTree(src); // Build Dominator Tree  
      dfs1(src);  
      ll ans = subtreeSize[src] - 1;  
      ll sum = 0;  
      for (int child : Tree[src])  
      {  
            ans += (ll)subtreeSize[child] * sum;  
            sum += subtreeSize[child];  
      }  
      cout << ans << endl;  
}