Skip to content

Dominator Tree

Background

The notion of dominance was introduced by Reese T. Prosser in 1959, in a paper on network flow, but with no concrete algorithm for computing it. Only in 1969 did Edward S. Lowry and C. W. Medlock give the first effective algorithm. The Lengauer–Tarjan algorithm, the most widely used today, was published by Lengauer and Tarjan in a 1979 paper.

In the OI community, dominator trees first appeared in ZJOI2012 Catastrophe, where they were also called "extinction trees"; Sunli Chen also presented the algorithm in one of the 2020 Chinese national training team papers.

Dominator trees are not popular in competitive programming at present, and problems on them are rare. In industry, however, and in compilers especially, they are widely used.

This article introduces dominator trees and several ways to compute them.

Dominance relation

Fix an entry vertex \(s\) in an arbitrary directed graph. For a vertex \(u\), if every path from \(s\) to \(u\) passes through some vertex \(v\), we say that \(v\) dominates \(u\), or that \(v\) is a dominator of \(u\), and write \(v\ dom\ u\).

Dominance is meaningless for vertices that cannot be reached from \(s\), so unless stated otherwise this article assumes that \(s\) can reach every vertex of the graph.

In this directed graph, for example, \(2\) is dominated by \(1\); \(3\) by \(1\) and \(2\); 4 by \(1\), \(2\) and \(3\); 5 by \(1\) and \(2\); and so on.

Lemmas

In the lemmas below we assume \(u, v, w\ne s\).

Lemma 1: \(s\) is a dominator of every vertex, and every vertex is a dominator of itself.

Proof: Every path from \(s\) to \(u\) must pass through both \(s\) and \(u\).

Lemma 2: Considering only simple paths gives the same dominance relation as considering all paths.

Proof: Given a non-simple path, let \(S\) be the set of all vertices it visits between two visits to the same vertex. Deleting the vertices of \(S\) maps every non-simple path to a simple path.

A vertex of \(S\) that lies on the non-simple path but not on the simple path cannot be a dominator, because at least one simple path from \(s\) to \(u\) avoids it. A vertex that lies on both paths only needs to be considered on the simple path.

So discarding the non-simple paths does not affect the dominance relation.

Lemma 3: If \(u\) \(dom\) \(v\) and \(v\) \(dom\) \(w\), then \(u\) \(dom\) \(w\).

Proof: A path that reaches \(w\) must pass through \(v\), and a path that passes through \(v\) must pass through \(u\). So a path that reaches \(w\) must pass through \(u\), that is, \(u \ dom \ w\).

Lemma 4: If \(u \ dom \ v\) and \(v \ dom\ u\), then \(u=v\).

Proof: Suppose \(u \ne v\). Then every path that reaches \(v\) has already visited \(u\), and every path that reaches \(u\) has already visited \(v\), a contradiction.

Lemma 5: If \(u \ne v \ne w\), \(u \ dom \ w\) and \(v \ dom \ w\), then \(u \ dom \ v\) or \(v \ dom \ u\).

Proof: Take a path \(s \rightarrow \dots \rightarrow u \rightarrow \dots \rightarrow v \rightarrow \dots \rightarrow w\). If neither of \(u\) and \(v\) dominates the other, there must be a path from \(s\) to \(v\) that avoids \(u\), and hence a path \(s \rightarrow \dots \rightarrow v \rightarrow \dots \rightarrow w\), which contradicts \(u\ dom\ w\).

Computing the dominance relation

Vertex deletion

The definition can be restated as follows: if deleting a vertex from the graph makes some vertices unreachable, then the deleted vertex dominates those vertices.

So we just delete each vertex in turn and run a DFS. The code runs in \(O(n^3)\); its core is shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// assume the graph has n vertices and the start vertex is s = 1
std::bitset<N> vis;
std::vector<int> edge[N];
std::vector<int> dom[N];

void dfs(int u, int del) {
  vis[u] = true;
  for (int v : edge[u]) {
    if (v == del or vis[v]) {
      continue;
    }
    dfs(v, del);
  }
}

void getdom() {
  for (int i = 2; i <= n; ++i) {
    vis.reset();
    dfs(1, i);
    for (int j = 1; j <= n; ++j) {
      if (!vis[j]) {
        dom[j].push_back(i);
      }
    }
  }
}

Iterative data-flow analysis

Iterative data-flow analysis is another topic that rarely comes up in OI, so here is a brief introduction first.

Data-flow analysis is a notion from compiler theory: it studies how data flows along the execution paths of a program. The iterative method sets up an equation at each vertex of the program's flow graph and solves the equations by repeated iteration, which gives the data-flow values at certain points of the program. Here we simply regard the directed graph as the flow graph of a program.

For this problem the equation is:

\[ dom(u)=\{u\} \cup \left(\bigcap_{v\in pre(u)}{dom(v)}\right) \]

Here \(pre(u)\) is the set of predecessors of \(u\). The equation follows from Lemma 3.

In plain words, the dominator set of a vertex is the intersection of the dominator sets of all its predecessors, plus the vertex itself. Apply the equation to the dominator set of every vertex again and again until nothing changes.

For efficiency, when a vertex is processed in a round, as many of its predecessors as possible should already have been processed in that round. So we find the reverse postorder of the graph with a depth-first search and iterate in that order.

A reference implementation of the core follows. It needs the predecessor set of every vertex and the reverse postorder of the graph to be computed beforehand; that is not the subject of this article, so no implementation is given for it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
std::vector<int> pre[N];  // predecessors of each vertex
std::vector<int> ord;     // reverse postorder of the graph
std::bitset<N> dom[N];
std::vector<int> Dom[N];

void getdom() {
  dom[1][1] = true;
  flag = true;
  while (flag) {
    flag = false;
    for (int u : ord) {
      std::bitset<N> tmp;
      tmp[u] = true;
      for (int v : pre[u]) {
        tmp &= dom[v];
      }
      if (tmp != dom[u]) {
        dom[u] = tmp;
        flag = true;
      }
    }
  }
  for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (dom[i][j]) {
        Dom[i].push_back(j);
      }
    }
  }
}

This algorithm runs in \(O(n^2)\).

Dominator tree

As the previous section shows, every vertex other than \(s\) has at least two dominators: \(s\) and itself.

Among the dominators of a vertex \(u\) other than \(u\) itself, the one closest to \(u\), say \(v\), is called the immediate dominator of \(u\), written \(idom(u) = v\). Clearly \(s\) has no immediate dominator, and every other vertex has exactly one.

For every vertex \(u\) other than \(s\), add an edge from \(idom(u)\) to \(u\). The result is a directed graph with \(n\) vertices and \(n - 1\) edges. By Lemmas 3 and 4, the dominance relation can never be circular, so these edges form no cycle and the graph is in fact a tree. We call this tree the dominator tree of the original graph.

Computing the dominator tree

From the dom sets

Consider the dominator set \(\{s_1, s_2, \dots, s_k\}\) of some vertex. There must be a path \(s \rightarrow \dots \rightarrow s_1 \rightarrow \dots \rightarrow s_2 \rightarrow \dots \rightarrow \dots \rightarrow s_k \rightarrow\dots \rightarrow u\). Clearly the immediate dominator of \(u\) is \(s_k\). The definition of the immediate dominator is therefore equivalent to the following:

Let \(S\) be the dominator set of a vertex \(u\). If \(v \in S\) satisfies \(\forall w \in S\setminus\{u,v\}, w\ dom \ v\), then \(idom(u)=v\).

So once the algorithms above have produced the dominator set of every vertex, this definition readily gives each vertex's immediate dominator, and from these we construct the dominator tree. Reference code follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
std::bitset<N> dom[N];
std::vector<int> Dom[N];
int idom[N];

void getidom() {
  for (int u = 2; u <= n; ++u) {
    for (int v : Dom[u]) {
      std::bitset<N> tmp = (dom[v] & dom[u]) ^ dom[u];
      if (tmp.count() == 1 and tmp[u]) {
        idom[u] = v;
        break;
      }
    }
  }
  for (int u = 2; u <= n; ++u) {
    e[idom[u]].push_back(u);
  }
}

Special case: trees

Clearly the dominator tree of a tree-shaped graph is the graph itself.

Special case: DAGs

A DAG has a nice property: if we process the vertices in topological order, an answer computed earlier is never affected by later ones. This lets us compute the dominator tree of a DAG quickly.

Note

The DAG here must have a single source. With several sources, the vertices dominated by the sources would have more than one parent in the dominator tree, so the dominance relation could no longer be expressed simply as a dominator tree.

Lemma 6: In a directed graph, \(v\ dom\ u\) if and only if \(\forall w \in pre(u), v\ dom \ w\).

Proof: First, sufficiency. Every path from \(s\) to \(u\) passes through some vertex \(w \in pre(u)\), and \(v\) dominates that vertex. So every path from \(s\) to \(u\) passes through \(v\), which gives \(v \ dom \ u\).

Now necessity. If \(\exists w\in pre(u)\) such that \(v\) does not dominate \(w\), there must be a path \(s \rightarrow \cdots \rightarrow w \rightarrow \cdots \rightarrow u\) that avoids \(v\), so \(v\) does not dominate \(u\).

Hence every dominator of \(u\) is a common ancestor, in the dominator tree, of all its predecessors, and the immediate dominator of \(u\) is their LCA in the dominator tree. Since LCA by binary lifting supports adding one vertex at a time, this algorithm clearly works.

A reference implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
std::stack<int> sta;
std::vector<int> e[N], g[N], tree[N];  // g is the transpose of the original graph, tree is the dominator tree
int n, s, in[N], tpn[N], dep[N], idom[N];  // n is the number of vertices, s is the start vertex, in is the in-degree
int fth[N][17];

void topo(int s) {
  sta.push(s);
  while (!sta.empty()) {
    int u = sta.top();
    sta.pop();
    tpn[++tot] = u;
    for (int v : e[u]) {
      --in[v];
      if (!in[v]) {
        sta.push(v);
      }
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    std::swap(u, v);
  }
  for (int i = 15; i >= 0; --i) {
    if (dep[fth[u][i]] >= dep[v]) {
      u = fth[u][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = 15; i >= 0; --i) {
    if (fth[u][i] != fth[v][i]) {
      u = fth[u][i];
      v = fth[v][i];
    }
  }
  return fth[u][0];
}

void build() {
  topo(s);
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= 15; ++j) fth[i][j] = s;
  for (int i = 1; i <= n; ++i) {
    int u = tpn[i];
    if (g[u].size()) {
      int v = g[u][0];
      for (int j = 1, q = g[u].size(); j < q; ++j) {
        v = lca(v, g[u][j]);
      }
      tree[v].push_back(u);
      fth[u][0] = v;
      dep[u] = dep[v] + 1;
      for (int i = 1; i <= 15; ++i) {
        fth[u][i] = fth[fth[u][i - 1]][i - 1];
      }
    }
  }
}

Lengauer–Tarjan algorithm

The Lengauer–Tarjan algorithm is one of the best-known algorithms for dominator trees: it computes the dominator tree of a directed graph in \(O(m\alpha(m, n))\) time. It introduces the notion of a semidominator and uses semidominators to help find the immediate dominators.

Conventions

First, run a DFS on the directed graph from \(s\). The vertices and edges it traverses form a tree \(T\). We call the traversed edges tree edges and the remaining ones non-tree edges. Let \(dfn(u)\) be the position of vertex \(u\) in the order of visits, and define \(u<v\) if and only if \(dfn(u) < dfn(v)\).

Semidominators

The semidominator of a vertex \(u\) is the smallest vertex \(v\) from which there is a path to \(u\) whose vertices, other than \(u\) and \(v\), are all greater than \(u\). Formally, the semidominator \(sdom(u)\) of \(u\) is defined as:

\(sdom(u) = \min(v|\exists v=v_0 \rightarrow v_1 \rightarrow\dots \rightarrow v_k = u, \forall 1\le i\le k - 1, v_i > u)\)

Semidominators have some useful properties:

Lemma 7: For every vertex \(u\), \(sdom(u) < u\).

Proof: By the definition, the parent \(fa(u)\) of \(u\) in \(T\) also satisfies the condition in the definition of the semidominator, and \(fa(u) < u\). So no vertex greater than \(u\) can be its semidominator.

Lemma 8: For every vertex \(u\), \(idom(u)\) is an ancestor of \(u\) in \(T\).

Proof: The path from \(s\) to \(u\) in \(T\) corresponds to a path in the original graph, so \(idom(u)\) must lie on it.

Lemma 9: For every vertex \(u\), \(sdom(u)\) is an ancestor of \(u\) in \(T\).

Proof: Suppose \(sdom(u)\) is not an ancestor of \(u\). Then \(sdom(u)\) cannot have an edge to any vertex whose \(\mathrm{dfs}\) order is greater than or equal to that of \(u\) (otherwise that vertex would be in the subtree of \(sdom(u)\) and not in another subtree), a contradiction.

Lemma 10: For every vertex \(u\), \(idom(u)\) is an ancestor of \(sdom(u)\).

Proof: We can go from \(s\) to \(sdom(u)\) and then follow the path from the definition to \(u\). By the definition, none of the vertices on the path from \(sdom(u)\) to \(u\) dominates \(u\), so \(idom(u)\) must be an ancestor of \(sdom(u)\).

Lemma 11: For any vertices \(u \ne v\) such that \(v\) is an ancestor of \(u\), either \(v\) is an ancestor of \(idom(u)\), or \(idom(u)\) is an ancestor of \(idom(v)\).

Proof: For any vertex \(w\) between \(v\) and \(idom(v)\), the definition of the immediate dominator guarantees a path from \(s\) to \(idom(v)\) and on to \(v\) that avoids \(w\). So none of these vertices \(w\) can be \(idom(u)\), and \(idom(u)\) is either a descendant of \(v\) or an ancestor of \(idom(v)\).

These lemmas lead to the following theorem:

Theorem 1: The semidominator of a vertex \(u\) is the smallest vertex among the predecessors of \(u\) and the semidominators of all ancestors in \(T\) of those predecessors that are greater than \(u\). Formally, \(sdom(u)=\min(\{v|\exists v \rightarrow u, v < u \} \cup \{sdom(w) | w > u\ and\ \exists w \rightarrow \dots \rightarrow v \rightarrow u \})\).

Proof: Let \(x\) be the right-hand side of the formula above.

We first prove \(sdom(u) \le x\). By Lemma 7, this is equivalent to showing that both kinds of vertices above satisfy the condition in the definition of the semidominator. The case where \(x\) is a predecessor of \(u\) is clear. For the second kind, take the path \(x=v_0\rightarrow\dots\rightarrow v_j=w\) described in the definition of the semidominator, a path \(w=v_j \rightarrow\dots\rightarrow v_k=v\) in \(T\), which satisfies \(\forall i\in[j, k-1], v_i\ge w > u\), and the path \(v \rightarrow u\). Concatenating the three gives a path that satisfies the definition of the semidominator.

Next we prove \(sdom(u)\ge x\). Take the path \(sdom(u)=v_0\rightarrow v_1 \rightarrow\dots\rightarrow v_k=u\) described in the definition of the semidominator of \(u\). The cases \(k=1\) and \(k > 1\) correspond to the two cases of the formula. If \(k = 1\), there is a directed edge \(sdom(u) \rightarrow u\), and the claim follows from Lemma 7. If \(k>1\), let \(j\) be the smallest number such that \(j \ge 1\) and \(v_j\) is an ancestor of \(v_{k-1}\) in \(T\). Such a \(j\) must exist, because \(k\) satisfies these conditions.

We now show that \(v_0 \rightarrow \dots \rightarrow v_j\) is a path that satisfies the condition in the definition of the semidominator of \(v_j\), that is, \(\forall i \in [1, j), v_i>v_j\). If not, let \(i\) be the index that minimizes \(v_i\) among those with \(v_i < v_j\). Then every vertex on the path \(v_i\rightarrow\dots\rightarrow v_j\) is at least \(v_i\), so by a property of DFS trees \(v_i\) must be an ancestor of \(v_j\), and hence of \(v_{k-1}\) as well, which contradicts the minimality of \(j\). Therefore \(sdom(v_j)\le sdom(u)\). Since \(x\le sdom(v_j)\), we get \(sdom(u)\ge x\). Together with \(sdom(u) \le x\), proved earlier, this gives \(x=sdom(u)\).

Theorem 1 lets us compute the semidominator of every vertex. The bottleneck is the second case. We speed it up with a weighted disjoint set union that updates the minimum on every path compression.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void dfs(int u) {
  dfn[u] = ++dfc;
  pos[dfc] = u;
  for (int i = h[0][u]; i; i = e[i].x) {
    int v = e[i].v;
    if (!dfn[v]) {
      dfs(v);
      fth[v] = u;
    }
  }
}

int find(int x) {
  if (fa[x] == x) {
    return x;
  }
  int tmp = fa[x];
  fa[x] = find(fa[x]);
  if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]]) {
    mn[x] = mn[tmp];
  }
  return fa[x];
}

void getsdom() {
  dfs(1);
  for (int i = 1; i <= n; ++i) {
    mn[i] = fa[i] = sdm[i] = i;
  }
  for (int i = dfc; i >= 2; --i) {
    int u = pos[i], res = INF;
    for (int j = h[1][u]; j; j = e[j].x) {
      int v = e[j].v;
      if (!dfn[v]) {
        continue;
      }
      find(v);
      if (dfn[v] < dfn[u]) {
        res = std::min(res, dfn[v]);
      } else {
        res = std::min(res, dfn[sdm[mn[v]]]);
      }
    }
    sdm[u] = pos[res];
    fa[u] = fth[u];
  }
}

Computing immediate dominators

Reduction to a DAG

But I still don't know what semidominators are good for!

For every \(u\), add the directed edge \(sdom(u) \rightarrow u\) to \(T\). By Lemma 9, the resulting graph \(G\) must be a directed acyclic graph. By Lemma 10, adding edges this way does not change the dominance relation. We have thus turned the original graph into a DAG, and the algorithm above solves it.

Directly from semidominators

Building a pile of graphs is far too inelegant!

Theorem 2: For any vertex \(u\), if every vertex \(v\) on the path in \(T\) from \(sdom(u)\) to \(u\) (excluding \(sdom(u)\)) satisfies \(sdom(v)\ge sdom(u)\), then \(idom(u) =sdom(u)\).

Proof: By Lemma 10, \(idom(u)\) is \(sdom(u)\) or one of its ancestors, so it suffices to prove \(sdom(u) \ dom \ u\).

Take any path \(P\) from \(s\) to \(u\); we must show that \(sdom(u)\) lies on \(P\). Let \(v\) be the last vertex on \(P\) with \(v<sdom(u)\). If no such \(v\) exists, then \(sdom(u)=idom(u) =s\). Otherwise, let \(w\) be the first vertex after \(v\) on \(P\) that lies on the DFS tree path from \(sdom(u)\) to \(u\).

Next we prove \(sdom(w)\le v <sdom(u)\). Consider the part \(v = v_0 \rightarrow \dots v_k = w\) of \(P\) from \(v\) to \(w\). If the claim fails, there exists \(i\in[1, k- 1], v_i < w\). Then there must be some \(j\in [i, k - 1]\) for which \(v_j\) is an ancestor of \(w\). By the choice of \(v\) we know that \(sdom(u)\le v_j\), so \(v_j\) also lies on the DFS tree path from \(sdom(u)\) to \(u\), which contradicts the definition of \(w\). Hence \(sdom(w)\le v < sdom(u)\). With the hypothesis of the theorem this gives \(w=sdom(u)\), that is, the path \(P\) contains \(sdom(u)\).

Theorem 3: For any vertex \(u\), let \(v\) be the vertex with the smallest semidominator among all vertices on the path in \(T\) from \(sdom(u)\) to \(u\) (excluding \(sdom(u)\)). Then \(sdom(v)\le sdom(u)\) and \(idom(v) = idom(u)\).

Proof: Since \(u\) itself is one of the candidates for \(v\), we have \(sdom(v)\le sdom(u)\).

Since \(idom(u)\) is an ancestor of \(v\) in \(T\), Lemma 11 shows that \(idom(u)\) is also an ancestor of \(idom(v)\), so it suffices to prove that \(idom(v)\) dominates \(u\).

Take any path \(P\) from \(s\) to \(u\); we must show that \(idom(v)\) lies on \(P\). Let \(x\) be the last vertex on \(P\) with \(x<idom(v)\). If no such \(x\) exists, then \(idom(v)=s\). Otherwise, let \(y\) be the first vertex after \(x\) on \(P\) that lies on the DFS tree path from \(idom(v)\) to \(u\).

As in the proof of Theorem 2, we get \(sdom(y) \le x\). By Lemma 10, \(sdom(y)\le x<idom(v) \le sdom(v)\). By the definition of \(v\), then, \(y\) cannot be a descendant of \(sdom(u)\). On the other hand, \(y\) cannot be both a descendant of \(idom(v)\) and an ancestor of \(v\): otherwise the path that follows the DFS tree from \(s\) to \(sdom(y)\), then follows P to \(y\), and finally follows the DFS tree to \(v\) would avoid \(idom(v)\), contradicting the definition of a dominator. Therefore \(y=idom(v)\), that is, \(P\) contains \(idom(v)\).

These two theorems give the relation between \(sdom(u)\) and \(idom(u)\).

Let \(v\) be the vertex with the smallest \(sdom(v)\) among all vertices on the path in \(T\) from \(sdom(u)\) to \(u\) (excluding \(sdom(u)\)). Then:

\[ idom(u) = \left\{ \begin{aligned} & sdom(u), &\text{if}\ sdom(u) = sdom(v) \\ &idom(v), &\text{otherwise} \end{aligned} \right. \]

A small change to the semidominator code above is all it takes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
struct E {
  int v, x;
} e[MAX * 4];

int h[3][MAX * 2];

int dfc, tot, n, m, u, v;
int fa[MAX], fth[MAX], pos[MAX], mn[MAX], idm[MAX], sdm[MAX], dfn[MAX],
    ans[MAX];

void add(int x, int u, int v) {
  e[++tot] = {v, h[x][u]};
  h[x][u] = tot;
}

void dfs(int u) {
  dfn[u] = ++dfc;
  pos[dfc] = u;
  for (int i = h[0][u]; i; i = e[i].x) {
    int v = e[i].v;
    if (!dfn[v]) {
      dfs(v);
      fth[v] = u;
    }
  }
}

int find(int x) {
  if (fa[x] == x) {
    return x;
  }
  int tmp = fa[x];
  fa[x] = find(fa[x]);
  if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]]) {
    mn[x] = mn[tmp];
  }
  return fa[x];
}

void tar(int st) {
  dfs(st);
  for (int i = 1; i <= n; ++i) {
    fa[i] = sdm[i] = mn[i] = i;
  }
  for (int i = dfc; i >= 2; --i) {
    int u = pos[i], res = INF;
    for (int j = h[1][u]; j; j = e[j].x) {
      int v = e[j].v;
      if (!dfn[v]) {
        continue;
      }
      find(v);
      if (dfn[v] < dfn[u]) {
        res = std::min(res, dfn[v]);
      } else {
        res = std::min(res, dfn[sdm[mn[v]]]);
      }
    }
    sdm[u] = pos[res];
    fa[u] = fth[u];
    add(2, sdm[u], u);
    u = fth[u];
    for (int j = h[2][u]; j; j = e[j].x) {
      int v = e[j].v;
      find(v);
      if (sdm[mn[v]] == u) {
        idm[v] = u;
      } else {
        idm[v] = mn[v];
      }
    }
    h[2][u] = 0;
  }
  for (int i = 2; i <= dfc; ++i) {
    int u = pos[i];
    if (idm[u] != sdm[u]) {
      idm[u] = idm[idm[u]];
    }
  }
}

Example problems

Luogu P5180 [Template] Dominator Tree

You can compute just the dominance relation, recording along the way how many vertices each vertex dominates, or build the dominator tree and compute the subtree size of every vertex.

The code below takes the second approach.

Reference code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <iostream>
using std::cin;
using std::cout;
constexpr int MAX = 3e5 + 5;
constexpr int INF = 0x5ffffff;

struct E {
  int v, x;
} e[MAX * 4];

int n, m, u, v, tot, dfc;
int ans[MAX], dfn[MAX], pos[MAX], sdm[MAX], idm[MAX], fa[MAX], mn[MAX],
    fth[MAX];
int h[3][MAX * 2];

void add(int x, int u, int v) {
  e[++tot] = {v, h[x][u]};
  h[x][u] = tot;
}

void dfs(int u) {
  dfn[u] = ++dfc;
  pos[dfc] = u;
  for (int i = h[0][u]; i; i = e[i].x) {
    int v = e[i].v;
    if (!dfn[v]) {
      dfs(v);
      fth[v] = u;
    }
  }
}

int find(int x) {
  if (fa[x] == x) {
    return x;
  }
  int tmp = fa[x];
  fa[x] = find(fa[x]);
  if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]]) {
    mn[x] = mn[tmp];
  }
  return fa[x];
}

void tar(int st) {
  dfs(st);
  for (int i = 1; i <= n; ++i) {
    mn[i] = fa[i] = sdm[i] = i;
  }
  for (int i = dfc; i >= 2; --i) {
    int u = pos[i], res = INF;
    for (int j = h[1][u]; j; j = e[j].x) {
      int v = e[j].v;
      if (!dfn[v]) {
        continue;
      }
      find(v);
      if (dfn[v] < dfn[u]) {
        res = std::min(res, dfn[v]);
      } else {
        res = std::min(res, dfn[sdm[mn[v]]]);
      }
    }
    sdm[u] = pos[res];
    fa[u] = fth[u];
    add(2, sdm[u], u);
    u = fth[u];
    for (int j = h[2][u]; j; j = e[j].x) {
      int v = e[j].v;
      find(v);
      if (u == sdm[mn[v]]) {
        idm[v] = u;
      } else {
        idm[v] = mn[v];
      }
    }
    h[2][u] = 0;
  }
  for (int i = 2; i <= dfc; ++i) {
    int u = pos[i];
    if (idm[u] != sdm[u]) {
      idm[u] = idm[idm[u]];
    }
  }
  for (int i = dfc; i >= 2; --i) {
    ++ans[pos[i]];
    ans[idm[pos[i]]] += ans[pos[i]];
  }
  ++ans[1];
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> u >> v;
    add(0, u, v);
    add(1, v, u);
  }
  tar(1);
  for (int i = 1; i <= n; ++i) {
    cout << ans[i] << ' ';
  }
}

ZJOI2012 Catastrophe

Compute the dominator tree of the DAG, then the subtree size of every vertex.

Reference code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <iostream>
#include <stack>
#include <vector>

using std::cin;
using std::cout;
using std::stack;
using std::vector;

constexpr int MAX = 65536;
int n, x, tot;
int d[MAX], w[MAX], siz[MAX], p[MAX], f[MAX][17];
vector<int> e[MAX], g[MAX], h[MAX];
stack<int> s;

void topo() {
  s.push(0);
  for (int i = 1; i <= n; ++i) {
    if (!w[i]) {
      e[0].push_back(i);
      g[i].push_back(0);
      ++w[i];
    }
  }
  while (!s.empty()) {
    int x = s.top();
    s.pop();
    p[++tot] = x;
    for (int i : e[x]) {
      --w[i];
      if (!w[i]) {
        s.push(i);
      }
    }
  }
}

int lca(int u, int v) {
  if (d[u] < d[v]) {
    std::swap(u, v);
  }
  for (int i = 15; i >= 0; --i) {
    if (d[f[u][i]] >= d[v]) {
      u = f[u][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = 15; i >= 0; --i) {
    if (f[u][i] != f[v][i]) {
      u = f[u][i];
      v = f[v][i];
    }
  }
  return f[u][0];
}

void dfs(int x) {
  siz[x] = 1;
  for (int i : h[x]) {
    dfs(i);
    siz[x] += siz[i];
  }
}

void build() {
  for (int i = 2; i <= n + 1; ++i) {
    int x = p[i], y = g[x][0];
    for (int j = 1, q = g[x].size(); j < q; ++j) {
      y = lca(y, g[x][j]);
    }
    h[y].push_back(x);
    d[x] = d[y] + 1;
    f[x][0] = y;
    for (int i = 1; i <= 15; ++i) {
      f[x][i] = f[f[x][i - 1]][i - 1];
    }
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    while (true) {
      cin >> x;
      if (!x) {
        break;
      }
      e[x].push_back(i);
      g[i].push_back(x);
      ++w[i];
    }
  }
  topo();
  build();
  dfs(0);
  for (int i = 1; i <= n; ++i) {
    cout << siz[i] - 1 << '\n';
  }
  return 0;
}