[Gym] 100513L - Useful Roads

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 100513L - Useful Roads
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 = 3e5 + 5;  
  
struct Node  
{  
      int v, e;  
      Node(int v = 0, int e = 0) : v(v), e(e) {}  
};  
  
vector <Node> graph[maxn], rgraph[maxn];  
vector <int> Tree[maxn], bucket[maxn];  
  
int arr[maxn], par[maxn], rev[maxn], sdom[maxn], dom[maxn],  
    dsu[maxn], label[maxn], dfsTime;  
  
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)  
{  
      dsu[v] = u;  
}  
  
void dfs(int u)  
{  
      ++dfsTime;  
      arr[u] = dfsTime;  
      rev[dfsTime] = u;  
      label[dfsTime] = dfsTime;  
      sdom[dfsTime] = dfsTime;  
      dsu[dfsTime] = dfsTime;  
      for (Node g : graph[u])  
      {  
            int v = g.v;  
            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].v) ]);  
            }  
            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 in[maxn], out[maxn], ptr;  
  
void dfs1(int u, int p = -1)  
{  
      in[u] = ++ptr;  
      for (int v : Tree[u])  
      {  
            if (v == p) continue;  
            dfs1(v, u);  
      }  
      out[u] = ++ptr;  
}  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
  
      int tnode, tedge;  
      while (cin >> tnode >> tedge)  
      {  
            for (int e = 1; e <= tedge; e++)  
            {  
                  int u, v;  
                  cin >> u >> v;  
                  graph[u].eb(v, e);  
            }  
            int src = 1;  
            DominatorTree(src);  
            dfs1(src);  
            vector <int> useful;  
            for (int u = 1; u <= tnode; u++)  
            {  
                  for (Node g : graph[u])  
                  {  
                        int v = g.v;  
                        int e = g.e;  
                        if (in[v] <= in[u] && out[v] >= out[u]) continue;  
                        if (arr[u] == 0 || arr[v] == 0) continue;  
                        useful.eb(e);  
                  }  
            }  
            sort(useful.begin(), useful.end());  
            int ans = sz(useful);  
            cout << ans << endl;  
            for (int r : useful) cout << r << " ";  
            cout << endl;  
  
            dfsTime = 0;  
            ptr = 0;  
            useful.clear();  
            for (int i = 1; i <= tnode; i++)  
            {  
                  graph[i].clear();  
                  rgraph[i].clear();  
                  Tree[i].clear();  
                  bucket[i].clear();  
                  arr[i] = 0;  
                  rev[i] = 0;  
                  par[i] = 0;  
                  sdom[i] = 0;  
                  dom[i] = 0;  
                  label[i] = 0;  
                  dsu[i] = 0;  
                  in[i] = 0;  
                  out[i] = 0;  
            }  
      }  
}