graph - Dominator Tree

/*
Dominator tree of a undirected graph.
1. Create a Dag
2. For each node, par = LCA( of its parent in Dag)
3. Sparse Table.

*/
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second


const int N = 2e5+5;
const int LG = 18;
long long d[N];
bool vis[N];
long long INF = 1e18;
vector<pair<int,long long> > G[N] ,Dag[N];
vector<int> top;
vector<int> par[N];
int P[N][LG];
int lev[N];
vector < int > T[N];
int Size[N];

int n,m,s,u,v,w;

void Dijkastra(int s,int n)
{
   for(int i=0;i<=n;i++) d[i]=INF, vis[i] =0;
   d[s]= 0;
   set<pair<long long,int> > pq;
   pq.insert(make_pair(d[s],s));
   while(!pq.empty()){
      auto p = *pq.begin(); pq.erase(pq.begin());
      int u= p.S;
      for(auto a: G[u]) {
         if(d[a.F] > a.S + d[u]) {
            d[a.F] = a.S + d[u];
            pq.insert(make_pair(d[a.F] , a.F));
         }
      }
   }
}

void BuildDag(int n)
{
   for(int i=1;i<=n;i++) {
      for(int j=0;j < G[i].size(); j++) {
         int v = G[i][j].F ;
         long long w = G[i][j].S;
         if(d[v] != INF && d[i] != INF && d[v ] == d[i] + w) {
            Dag[i].push_back(make_pair(v,w));
            par[v].push_back(i);
         }
      }
   }
}
void dfs(int s)
{
   if(vis[s]) return ;
   vis[s] = 1;
   for(auto a: Dag[s]) {
      dfs(a.F);
   }
   top.push_back(s);
}
void Topsort(int s)
{
   memset(vis,0,sizeof vis);
   top.clear();
   dfs(s);
   reverse(top.begin(), top.end());
}

int LCA(int u,int v)
{
   if(lev[u] > lev[v]) swap(u,v);
   int d = lev[v] - lev[u];
   for(int i = LG - 1; i >= 0 ;  i -- ) if( d  &1<<i) v = P[v][i];

   if(u==v) return u;

   for(int i = LG-1; i >= 0 ; i -- ) {
      if(P[u][i] != P[v][i]) {
         u = P[u][i];
         v = P[v][i];
      }
   }
   return P[v][0];
}
void BuildDom(int n)
{
   memset(P,-1,sizeof P);
   memset(lev,0,sizeof lev);
   for(int i= 0;i < top.size(); i++ ) {
      int u = top[i];
      if(par[u].size()){
         int lca = par[u][0];
         for(int i = 1; i < par[u].size(); i ++ ) {
            lca = LCA(lca, par[u][i]);
         }
         P[u][0] = lca;
         lev[u] = 1 + lev[lca];
         T[lca].push_back(u);
         for(int j= 1; j < LG ; j ++ ) if(P[u][j-1] !=-1 ) P[u][j] = P[P[u][j-1]][j-1];
      }
   }
}
void Dfs(int u)
{
   Size[u] = 1;
   for(auto a: T[u]) {
      Dfs(a);
      Size[u] += Size[a];
   }
}
int main()
{
   scanf("%d %d %d",&n,&m,&s);
   for(int i=0;i<m;i++){
      scanf("%d %d %d",&u,&v,&w);
      G[u].push_back(make_pair(v,w));
      G[v].push_back(make_pair(u,w));
   }
   Dijkastra(s,n);
   BuildDag(n);
   Topsort(s);
   BuildDom(n);
   Dfs(s);
   int ans = 0;
   for(int i = 1;i <= n;i ++) {
      if(i==s) continue;
      ans = max( ans, Size[i]);
   }
   printf("%d\n",ans);
}