🗂️Data StructureAdvanced

Dominator Tree

Key Points

•
A dominator tree summarizes “must-pass” relationships in a directed graph from a chosen root r: u dominates v if every path from r to v goes through u.
•
The parent of v in the dominator tree is its immediate dominator idom(v), the closest strict dominator of v; the root dominates all reachable vertices and is its own immediate dominator.
•
The Lengauer–Tarjan algorithm computes dominator trees in O(E $α (V))$ (almost linear) time using DFS order, semidominators, and a union-find with path compression.
•
Ancestors in the dominator tree are exactly the dominators in the original graph; this makes dominance queries O(1) after an Euler tour.
•
Dominator trees are heavily used in compiler control-flow analysis for optimizations like SSA, dead code elimination, and code motion.
•
In networks and competitive programming, they help find critical “must-pass” vertices, bottlenecks, and common dominators (via LCA on the dominator tree).
•
Implementation pitfalls include mixing original indices with DFS numbers, ignoring unreachable nodes, and forgetting the second pass that fixes idom values.
•
Pick the right root; dominance is defined with respect to that root only, and unreachable vertices have no immediate dominator.

Prerequisites

→Directed graphs and reachability — Dominance is defined on directed graphs with respect to a root; you must understand DFS/BFS reachability.
→Depth-First Search (DFS) and preorder numbering — The Lengauer–Tarjan algorithm relies on DFS order to define semidominators and build the evaluation structure.
→Union-Find (Disjoint Set Union) and path compression — eval/link operations use a union-find-like structure to achieve near-linear time.
→Tree traversal and Euler tour — To answer dominance queries quickly, we test ancestry in the dominator tree via tin/tout times.
→Lowest Common Ancestor (LCA) / Binary lifting — Closest common dominators of multiple nodes are LCAs in the dominator tree.
→Control-Flow Graphs (CFG) basics — Dominance is classically applied to CFGs in compilers, motivating the structure and typical use cases.

Detailed Explanation

Tap terms for definitions

01Overview

A dominator tree is a structural summary of a directed graph rooted at a chosen start node r. For any node v reachable from r, a node u is said to dominate v if every path from r to v includes u. The dominator tree connects each node v to its immediate dominator idom(v): the unique dominator of v that is closest to v along any path starting at r. This tree compactly encodes all dominance relationships: u dominates v in the graph if and only if u is an ancestor of v in the dominator tree.

Why is this useful? In compiler design, the graph is a control-flow graph (CFG), the root is the entry block, and dominance tells us what blocks must execute before others. This underpins Static Single Assignment (SSA) form, dead code elimination, loop-invariant code motion, and many other optimizations. Beyond compilers, dominator trees reveal vertices that are unavoidable for reaching certain targets, useful in network reliability, security analysis, and bottleneck detection.

Computing the dominator tree efficiently is nontrivial. The classic solution is the Lengauer–Tarjan algorithm, which runs in near-linear time. It performs a DFS to assign numbers, computes semidominators using a union-find data structure with path compression (specialized eval/link operations), and then derives immediate dominators. The final product is a rooted tree where each node’s parent is its immediate dominator, enabling fast dominance queries and further algorithms like LCA (Lowest Common Ancestor) on the dominator tree.

02Intuition & Analogies

Imagine a city map of one-way streets (a directed graph) with a single entry gate r. You want to understand which intersections are “must-pass” for reaching other intersections. If every possible route from the gate r to intersection v must go through intersection u, then u dominates v. In this sense, u is a checkpoint that cannot be avoided on the way to v.

Now picture building a hierarchy of checkpoints. For every intersection v, pick the closest unavoidable checkpoint on the way from r—this is the immediate dominator idom(v). If you draw an arrow from idom(v) to v for all intersections, you get a tree. Why a tree? Because each place has exactly one closest unavoidable checkpoint, and following these arrows always leads back to the entry gate r. This tree is a roadmap of control: to reach any spot, you must pass its ancestors in the tree.

How do we find this tree efficiently? First, walk the city from r and assign a visiting order (DFS numbers). Next, for each spot v, ask: what is the earliest place (in DFS order) that can still reach v while avoiding v’s DFS ancestors as much as possible? That’s the semidominator. Using a clever union-find with path compression (think of compressing road descriptions to quickly jump to the most relevant checkpoint), we compute these semidominators. Finally, from the semidominators we derive each node’s immediate dominator. Once we have the dominator tree, answering “does u dominate v?” is as simple as checking whether u is an ancestor of v in this tree—just like seeing if one checkpoint lies on the unique route from the root to another in the hierarchy.

03Formal Definition

Let G = (V, E) be a directed graph and r ∈ V a designated root. A node u ∈ V dominates v ∈ V (written u ⪯ v) if every directed path P from r to v contains u. By convention, every node dominates itself, and r dominates all nodes reachable from r. The immediate dominator of

v \neq = r

, denoted idom(v), is the unique strict dominator u of v such that for any other strict dominator w of v, we have u ⪯ w. Equivalently, idom(v) is the closest dominator to v along any

r \to v

path. The dominator tree T is the directed tree on the set of vertices reachable from r where each

v \neq = r

has parent idom(v), and r is the root. A fundamental property is: for any u, v reachable from r, u dominates v if and only if u is an ancestor of v in T. The Lengauer–Tarjan algorithm defines the semidominator of v in terms of a DFS spanning tree rooted at r with preorder numbers dfs(u). The semidominator semi(v) corresponds to the minimum (by dfs number) of nodes u that can reach v along a path whose internal nodes have dfs numbers greater than dfs(v). Using specialized union-find operations

\frac{e v a l}{l ink}

on the DFS tree, the algorithm computes semi(·) and then idom(·) in O(E

α (V))

or O(E log V) time, where α is the inverse Ackermann function.

04When to Use

Compiler analysis: In control-flow graphs, dominance is central to building SSA form (dominance and dominance frontiers), code motion (hoisting computations to dominating blocks), dead code elimination, and loop detection (natural loops and backedges).
Security and reliability: To find “must-pass” vertices that any attack or data flow must traverse, or to identify bottlenecks whose failure disconnects many downstream nodes from the source.
Network analysis: In directed communication, transport, or dependency networks, dominator trees mark critical relays needed to reach certain components from a source.
Program optimization and verification: Dominators formalize precondition blocks that must execute before others, enabling reasoning about variable definitions and reachability.
Competitive programming: Rare but appears in advanced problems asking for vertices that are unavoidable for reaching a set of targets, or for the closest common dominator (LCA on the dominator tree). Use it when the graph is directed, a single root is specified, and “must-pass” queries matter. If the graph is undirected or no single root is meaningful, dominator trees are not appropriate (consider bridges/articulation points instead).

⚠️Common Mistakes

Wrong or inconsistent root: Dominance is defined with respect to a chosen root r. Changing r changes the dominator tree. Always ensure the root is correct for the problem (e.g., CFG entry block).
Ignoring unreachable vertices: Nodes not reachable from r have no immediate dominator (idom = −1). Do not include them in the dominator tree; handle them separately in output and queries.
Mixing original indices with DFS numbers: The Lengauer–Tarjan algorithm works in DFS-number space. A very common bug is to use original vertex IDs where DFS indices are required (or vice versa). Carefully map between them at all steps.
Forgetting predecessors: The semidominator step needs the list of predecessors pred[v] restricted to reachable nodes. Building pred on the fly without DFS filtering leads to incorrect results.
Omitting the second pass to finalize idom: After the main loop, you must correct idom[v] by idom[v] = idom[idom[v]] when idom[v] ≠ semi[v]. Skipping this yields wrong parents.
Off-by-one and 0/1-based errors: The classic implementation numbers DFS from 1..N. Be consistent; mismatches cause ancestor checks and buckets to fail.
Misinterpreting results: Dominance in a directed graph is different from articulation points/bridges (undirected). Also, ancestors in the dominator tree correspond to dominators—don’t test dominance on the original graph’s paths directly after building the tree.

Key Formulas

Dominance definition

u dominates v ⟺ \forall paths P : r \to v, u \in P

Explanation: A node u dominates v if every directed path from the root r to v must pass through u. This captures the idea of a must-pass checkpoint for v.

Immediate dominator

idom (v) = the unique u \neq = v s.t. u strictly dominates v and ∄ w with u ≺ w ≺ v

Explanation: The immediate dominator of v is its closest strict dominator in the dominance partial order. It becomes v’s parent in the dominator tree.

Semidominator (DFS-based)

semi (v) = min {dfs (u) ∣ \exists u ⇝ v with all internal nodes x having dfs (x) > dfs (v)}

Explanation: Using the DFS preorder numbers, the semidominator of v is the earliest-numbered vertex that can reach v via a path that does not climb above v in the DFS tree except at the endpoints.

Lengauer–Tarjan time complexity

T (V, E) = O (E α (V))

Explanation: The algorithm runs in near-linear time using union-find with path compression, where α is the inverse Ackermann function, effectively a small constant in practice.

Ancestor equivalence

u dominates v ⟺ u is an ancestor of v in the dominator tree T

Explanation: The dominator tree encodes dominance: being an ancestor in T is equivalent to dominating in the original graph. This enables constant-time dominance checks after an Euler tour.

Closest common dominator

LCD (S) = LCA_{T} (S)

Explanation: The closest common dominator of a set of nodes S equals their lowest common ancestor in the dominator tree T. Use LCA to compute it efficiently.

Dominated subtree size

dominated_subtree_size (u) = 1 + (u, w) \in T \sum dominated_subtree_size (w)

Explanation: The number of nodes dominated by u equals the size of u’s subtree in the dominator tree. Sum the sizes of children plus one for u itself.

Inverse Ackermann (informal)

α (n) = min {k ∣ A (k, 4) \geq n}

Explanation: $α (n)$ grows so slowly that for any realistic input size it $i s \leq 4$ . This explains why O(E $α (V))$ behaves almost like O(E) in practice.

Euler tour ancestor test

Euler ancestor test: u ancestor of v ⟺ tin [u] \leq tin [v] \land tout [v] \leq tout [u]

Explanation: After a DFS over the dominator tree, use entry and exit times to check ancestry in O(1). This yields O(1) dominance queries.

Complexity Analysis

The Lengauer–Tarjan algorithm achieves near-linear time by combining three phases. First, a single DFS from the root r numbers the reachable vertices 1..N and records the DFS parent for each vertex. This costs O(V+E). Second, it computes semidominators using a specialized union-find structure equipped with path compression via eval/link operations. Each edge contributes a constant-amortized amount of work to find the best label along ancestor chains; with path compression, the total is O(E

α (V)),

where α is the inverse Ackermann function. Third, a final pass corrects immediate dominators by at most one additional pointer jump per vertex (idom[v] = idom[idom[v)] when needed), adding only O(V). Space usage is linear. We store the original adjacency, a predecessor list pred[v] for reachable vertices, DFS-order mappings (dfn and reverse), and several arrays of size O(V): semi, idom, parent, label, ancestor, and buckets for semidominator candidates. The dominator tree itself is another O(V) adjacency list. If we augment the structure with Euler tour arrays (tin, tout), that adds O(V). If we further add LCA via binary lifting, we store O(V log V) ancestors, which is still practical for typical constraints (e.g., V up to 2e5 with ~18–20 levels). In practice, the algorithm runs very fast on sparse graphs. For dense graphs (E ≈

V^{2}

), time is dominated by O(E). Dominance queries after construction are O(1) using an Euler tour, and LCA queries on the dominator tree are O(log V) with binary lifting or O(1) with RMQ-based methods. Overall, the heavy computation is the one-time dominator tree build; subsequent analyses and queries are cheap.

Code Examples

Build a dominator tree with Lengauer–Tarjan and print immediate dominators

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct DominatorTree {
5     int n, root;                          // number of nodes and chosen root (0-based)
6     vector<vector<int>> adj;              // directed graph
7 
8     // DFS numbering and mappings
9     vector<int> dfn, rev;                 // dfn[u] in [1..N] or 0 if unreachable; rev[i] -> original node
10     vector<int> parentIdx;                // parent in DFS tree (by DFS index)
11 
12     // LT arrays (indexed by DFS index 1..N)
13     vector<int> semi, idom, ancestor, label;
14     vector<vector<int>> pred, bucket;     // predecessors and buckets by DFS index
15     int N = 0;                            // number of reachable nodes
16 
17     // Dominator tree (original node indices)
18     vector<vector<int>> domTree;
19 
20     DominatorTree(int n): n(n) {
21         adj.assign(n, {});
22     }
23 
24     void add_edge(int u, int v) { adj[u].push_back(v); }
25 
26     void build(int r) {
27         root = r;
28         dfn.assign(n, 0);
29         rev.assign(n+1, -1);
30         vector<int> parentOrig(n, -1);
31         // DFS to number reachable nodes
32         N = 0;
33         function<void(int,int)> dfs = [&](int u, int p){
34             parentOrig[u] = p;
35             dfn[u] = ++N;
36             rev[N] = u;
37             for (int v : adj[u]) if (!dfn[v]) dfs(v, u);
38         };
39         dfs(root, -1);
40 
41         // Prepare LT arrays sized by N (reachable vertices only)
42         semi.assign(N+1, 0); idom.assign(N+1, 0); ancestor.assign(N+1, 0); label.assign(N+1, 0);
43         pred.assign(N+1, {}); bucket.assign(N+1, {}); parentIdx.assign(N+1, 0);
44 
45         // Build predecessor lists and parent indices in DFS-number space
46         for (int u = 0; u < n; ++u) if (dfn[u]) {
47             for (int v : adj[u]) if (dfn[v]) {
48                 pred[dfn[v]].push_back(dfn[u]);
49             }
50         }
51         for (int i = 1; i <= N; ++i) {
52             int u = rev[i];
53             semi[i] = label[i] = i;
54             if (i == 1) parentIdx[i] = 0; // root has no parent in DFS-indexed tree
55             else parentIdx[i] = dfn[parentOrig[u]];
56         }
57 
58         // eval/link with path compression
59         auto compress = [&](auto&& self, int v) -> void {
60             if (ancestor[ancestor[v]] != 0) {
61                 self(self, ancestor[v]);
62                 if (semi[label[ancestor[v]]] < semi[label[v]]) label[v] = label[ancestor[v]];
63                 ancestor[v] = ancestor[ancestor[v]];
64             }
65         };
66         auto eval = [&](auto&& self, int v) -> int {
67             if (ancestor[v] == 0) return label[v];
68             self(self, v);
69             return (semi[label[ancestor[v]]] < semi[label[v]]) ? label[ancestor[v]] : label[v];
70         };
71         auto link = [&](int u, int v){ ancestor[v] = u; };
72 
73         // Main LT loop: compute semidominators and idoms (provisional)
74         for (int i = N; i >= 2; --i) {
75             for (int v : pred[i]) {
76                 int u = eval(eval, v);
77                 if (semi[i] > semi[u]) semi[i] = semi[u];
78             }
79             bucket[semi[i]].push_back(i);
80             link(parentIdx[i], i);
81             for (int w : bucket[parentIdx[i]]) {
82                 int u = eval(eval, w);
83                 idom[w] = (semi[u] < semi[w] ? u : parentIdx[i]);
84             }
85             bucket[parentIdx[i]].clear();
86         }
87         for (int i = 2; i <= N; ++i) {
88             if (idom[i] != semi[i]) idom[i] = idom[idom[i]];
89         }
90 
91         // Build dominator tree in original indices
92         domTree.assign(n, {});
93         for (int i = 2; i <= N; ++i) {
94             int v = rev[i];
95             int p = rev[idom[i]];
96             domTree[p].push_back(v);
97         }
98     }
99 };
100 
101 int main() {
102     ios::sync_with_stdio(false);
103     cin.tie(nullptr);
104 
105     int n, m, r;
106     // Input: n m r, then m edges u v (0-based). r is the root.
107     if (!(cin >> n >> m >> r)) return 0;
108     DominatorTree DT(n);
109     for (int i = 0; i < m; ++i) {
110         int u, v; cin >> u >> v; DT.add_edge(u, v);
111     }
112     DT.build(r);
113 
114     // Print immediate dominator of each node (original indices).
115     // Convention: idom[root] = root; unreachable -> -1
116     vector<int> idom_out(n, -1);
117     if (DT.dfn[r]) idom_out[r] = r;
118     for (int v = 0; v < n; ++v) if (DT.dfn[v] && v != r) {
119         int idx = DT.dfn[v];
120         int parent_idx = DT.idom[idx];
121         idom_out[v] = DT.rev[parent_idx];
122     }
123 
124     for (int v = 0; v < n; ++v) cout << idom_out[v] << (v+1==n?'\n':' ');
125     return 0;
126 }
127

This program builds the dominator tree of a directed graph from a chosen root using the Lengauer–Tarjan algorithm. It numbers reachable vertices by DFS, constructs predecessor lists, computes semidominators and provisional immediate dominators with eval/link and path compression, finalizes idoms, and outputs each node’s immediate dominator (root dominates itself; unreachable nodes are −1).

Time: O(E α(V)) to build the dominator tree; O(V) to output idoms.Space: O(V+E) for graph, LT arrays, and the dominator tree.

Fast dominance queries and dominated subtree sizes (Euler tour on the dominator tree)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct DominatorTree {
5     int n, root;                          
6     vector<vector<int>> adj;              
7 
8     vector<int> dfn, rev, parentIdx;     
9     vector<int> semi, idom, ancestor, label;
10     vector<vector<int>> pred, bucket;     
11     int N = 0;                           
12 
13     vector<vector<int>> domTree;          
14     vector<int> tin, tout, sub, reachable;
15     int timerEuler = 0;
16 
17     DominatorTree(int n): n(n) { adj.assign(n, {}); }
18     void add_edge(int u, int v) { adj[u].push_back(v); }
19 
20     void build(int r) {
21         root = r;
22         dfn.assign(n, 0); rev.assign(n+1, -1);
23         vector<int> parentOrig(n, -1);
24         N = 0;
25         function<void(int,int)> dfs = [&](int u, int p){
26             parentOrig[u] = p; dfn[u] = ++N; rev[N] = u;
27             for (int v: adj[u]) if (!dfn[v]) dfs(v, u);
28         }; dfs(root, -1);
29 
30         semi.assign(N+1,0); idom.assign(N+1,0); ancestor.assign(N+1,0); label.assign(N+1,0);
31         pred.assign(N+1,{}); bucket.assign(N+1,{}); parentIdx.assign(N+1,0);
32         for (int u=0; u<n; ++u) if (dfn[u]) for (int v: adj[u]) if (dfn[v]) pred[dfn[v]].push_back(dfn[u]);
33         for (int i=1;i<=N;++i){ semi[i]=label[i]=i; parentIdx[i]=(i==1?0:dfn[parentOrig[rev[i]]]); }
34 
35         auto compress = [&](auto&& self, int v)->void{
36             if (ancestor[ancestor[v]] != 0){ self(self, ancestor[v]); if (semi[label[ancestor[v]]] < semi[label[v]]) label[v] = label[ancestor[v]]; ancestor[v] = ancestor[ancestor[v]]; }
37         };
38         auto eval = [&](auto&& self, int v)->int{
39             if (ancestor[v]==0) return label[v]; self(self, v); return (semi[label[ancestor[v]]] < semi[label[v]]) ? label[ancestor[v]] : label[v];
40         };
41         auto link = [&](int u,int v){ ancestor[v]=u; };
42 
43         for (int i=N;i>=2;--i){
44             for (int v: pred[i]){ int u = eval(eval, v); if (semi[i] > semi[u]) semi[i] = semi[u]; }
45             bucket[semi[i]].push_back(i); link(parentIdx[i], i);
46             for (int w: bucket[parentIdx[i]]){ int u = eval(eval, w); idom[w] = (semi[u] < semi[w] ? u : parentIdx[i]); }
47             bucket[parentIdx[i]].clear();
48         }
49         for (int i=2;i<=N;++i) if (idom[i] != semi[i]) idom[i] = idom[idom[i]];
50 
51         domTree.assign(n, {});
52         for (int i=2;i<=N;++i){ int v = rev[i]; int p = rev[idom[i]]; domTree[p].push_back(v); }
53 
54         // Euler tour for O(1) ancestor checks, and subtree sizes
55         tin.assign(n, -1); tout.assign(n, -1); sub.assign(n, 0); reachable.assign(n, 0);
56         for (int v=0; v<n; ++v) if (dfn[v]) reachable[v]=1; // mark reachable
57         timerEuler = 0;
58         function<void(int)> dfs2 = [&](int u){
59             tin[u] = ++timerEuler; sub[u] = 1;
60             for (int w: domTree[u]){ dfs2(w); sub[u] += sub[w]; }
61             tout[u] = timerEuler;
62         };
63         if (reachable[root]) dfs2(root);
64     }
65 
66     bool dominates(int u, int v) const { // true if u dominates v
67         if (u<0||u>=n||v<0||v>=n) return false;
68         if (tin[u]==-1 || tin[v]==-1) return false; // unreachable
69         return tin[u] <= tin[v] && tout[v] <= tout[u];
70     }
71 
72     int dominated_subtree_size(int u) const { // count of vertices dominated by u
73         if (u<0||u>=n || tin[u]==-1) return 0; return sub[u];
74     }
75 };
76 
77 int main(){
78     ios::sync_with_stdio(false);
79     cin.tie(nullptr);
80 
81     int n, m, r; cin >> n >> m >> r;
82     DominatorTree DT(n);
83     for (int i=0;i<m;++i){ int u,v; cin >> u >> v; DT.add_edge(u,v); }
84     DT.build(r);
85 
86     int q; cin >> q; // queries: type t, u v
87     // t=1: does u dominate v?  t=2: size of dominated subtree of u
88     while (q--){
89         int t; cin >> t;
90         if (t==1){ int u,v; cin >> u >> v; cout << (DT.dominates(u,v)?"YES":"NO") << '\n'; }
91         else if (t==2){ int u; cin >> u; cout << DT.dominated_subtree_size(u) << '\n'; }
92     }
93     return 0;
94 }
95

After constructing the dominator tree, the code performs an Euler tour to get tin/tout times and subtree sizes. Dominance queries reduce to ancestor checks (tin[u] ≤ tin[v] ≤ tout[u]), and the number of nodes dominated by u equals the size of u’s subtree in the dominator tree.

Time: Build: O(E α(V)). Each query: O(1).Space: O(V+E) plus O(V) for tin/tout/sub arrays.

Closest common dominator for a set of vertices via LCA on the dominator tree

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct DominatorTree {
5     int n, root; vector<vector<int>> adj;
6     vector<int> dfn, rev, parentIdx, semi, idom, ancestor, label; int N=0;
7     vector<vector<int>> pred, bucket, domTree;
8 
9     // LCA
10     int LOG=0; vector<int> depth; vector<vector<int>> up; vector<int> tin, tout; int timer=0;
11 
12     DominatorTree(int n): n(n){ adj.assign(n, {}); }
13     void add_edge(int u,int v){ adj[u].push_back(v); }
14 
15     void build(int r){
16         root=r; dfn.assign(n,0); rev.assign(n+1,-1); vector<int> parentOrig(n,-1); N=0;
17         function<void(int,int)> dfs = [&](int u,int p){ parentOrig[u]=p; dfn[u]=++N; rev[N]=u; for(int v:adj[u]) if(!dfn[v]) dfs(v,u); };
18         dfs(root,-1);
19         semi.assign(N+1,0); idom.assign(N+1,0); ancestor.assign(N+1,0); label.assign(N+1,0);
20         pred.assign(N+1,{}); bucket.assign(N+1,{}); parentIdx.assign(N+1,0);
21         for(int u=0;u<n;++u) if(dfn[u]) for(int v:adj[u]) if(dfn[v]) pred[dfn[v]].push_back(dfn[u]);
22         for(int i=1;i<=N;++i){ semi[i]=label[i]=i; parentIdx[i]=(i==1?0:dfn[parentOrig[rev[i]]]); }
23         auto compress = [&](auto&& self,int v)->void{ if(ancestor[ancestor[v]]!=0){ self(self,ancestor[v]); if(semi[label[ancestor[v]]]<semi[label[v]]) label[v]=label[ancestor[v]]; ancestor[v]=ancestor[ancestor[v]]; } };
24         auto eval = [&](auto&& self,int v)->int{ if(ancestor[v]==0) return label[v]; self(self,v); return (semi[label[ancestor[v]]]<semi[label[v]])?label[ancestor[v]]:label[v]; };
25         auto link = [&](int u,int v){ ancestor[v]=u; };
26         for(int i=N;i>=2;--i){ for(int v:pred[i]){ int u=eval(eval,v); if(semi[i]>semi[u]) semi[i]=semi[u]; } bucket[semi[i]].push_back(i); link(parentIdx[i],i); for(int w:bucket[parentIdx[i]]){ int u=eval(eval,w); idom[w]=(semi[u]<semi[w]?u:parentIdx[i]); } bucket[parentIdx[i]].clear(); }
27         for(int i=2;i<=N;++i) if(idom[i]!=semi[i]) idom[i]=idom[idom[i]];
28         domTree.assign(n,{}); for(int i=2;i<=N;++i){ int v=rev[i]; int p=rev[idom[i]]; domTree[p].push_back(v); }
29 
30         // Build LCA over the dominator tree (reachable subgraph)
31         LOG = 1; while ((1<<LOG) <= n) ++LOG;
32         up.assign(LOG, vector<int>(n, -1)); depth.assign(n, 0); tin.assign(n,-1); tout.assign(n,-1); timer=0;
33         function<void(int,int)> dfs2 = [&](int u,int p){ tin[u]=++timer; up[0][u]=(p==-1?u:p); for(int k=1;k<LOG;++k) up[k][u]=up[k-1][ up[k-1][u] ]; for(int v:domTree[u]){ depth[v]=depth[u]+1; dfs2(v,u);} tout[u]=timer; };
34         if (dfn[root]) dfs2(root,-1);
35     }
36 
37     bool reachable(int v) const { return v>=0 && v<n && dfn[v]!=0; }
38     bool is_ancestor(int u,int v) const { return tin[u]!=-1 && tin[v]!=-1 && tin[u]<=tin[v] && tout[v]<=tout[u]; }
39 
40     int lca(int u,int v) const { // LCA in dominator tree (assumes both reachable)
41         if (is_ancestor(u,v)) return u; if (is_ancestor(v,u)) return v;
42         int x=v; for(int k=LOG-1;k>=0;--k){ int a=up[k][x]; if(a!=-1 && !is_ancestor(a,u)) x=a; }
43         return up[0][x];
44     }
45 
46     int closest_common_dominator(const vector<int>& nodes) const {
47         int cur = -1;
48         for (int v : nodes) if (reachable(v)) { cur = (cur==-1? v : lca(cur, v)); }
49         return cur; // -1 if none reachable; otherwise LCA in dom tree
50     }
51 };
52 
53 int main(){
54     ios::sync_with_stdio(false); cin.tie(nullptr);
55     int n,m,r; cin>>n>>m>>r; DominatorTree DT(n); for(int i=0;i<m;++i){int u,v;cin>>u>>v;DT.add_edge(u,v);} DT.build(r);
56     int q; cin>>q; // each query: k followed by k nodes; output closest common dominator (or -1 if none reachable)
57     while(q--){
58         int k; cin>>k; vector<int> S(k); for(int i=0;i<k;++i) cin>>S[i];
59         int ans = DT.closest_common_dominator(S);
60         cout << ans << '\n';
61     }
62     return 0;
63 }
64

This program builds the dominator tree and then prepares a binary-lifting LCA structure over it. The closest common dominator of a set S equals their LCA in the dominator tree; queries reduce to LCA over reachable nodes.

Time: Build: O(E α(V)) + O(V log V) for LCA preprocessing. Each LCA query over k nodes: O(k log V).Space: O(V+E) for the dominator tree plus O(V log V) for LCA tables.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct DominatorTree {
5	int n, root; // number of nodes and chosen root (0-based)
6	vector<vector<int>> adj; // directed graph
7
8	// DFS numbering and mappings
9	vector<int> dfn, rev; // dfn[u] in [1..N] or 0 if unreachable; rev[i] -> original node
10	vector<int> parentIdx; // parent in DFS tree (by DFS index)
11
12	// LT arrays (indexed by DFS index 1..N)
13	vector<int> semi, idom, ancestor, label;
14	vector<vector<int>> pred, bucket; // predecessors and buckets by DFS index
15	int N = 0; // number of reachable nodes
16
17	// Dominator tree (original node indices)
18	vector<vector<int>> domTree;
19
20	DominatorTree(int n): n(n) {
21	adj.assign(n, {});
22	}
23
24	void add_edge(int u, int v) { adj[u].push_back(v); }
25
26	void build(int r) {
27	root = r;
28	dfn.assign(n, 0);
29	rev.assign(n+1, -1);
30	vector<int> parentOrig(n, -1);
31	// DFS to number reachable nodes
32	N = 0;
33	function<void(int,int)> dfs = [&](int u, int p){
34	parentOrig[u] = p;
35	dfn[u] = ++N;
36	rev[N] = u;
37	for (int v : adj[u]) if (!dfn[v]) dfs(v, u);
38	};
39	dfs(root, -1);
40
41	// Prepare LT arrays sized by N (reachable vertices only)
42	semi.assign(N+1, 0); idom.assign(N+1, 0); ancestor.assign(N+1, 0); label.assign(N+1, 0);
43	pred.assign(N+1, {}); bucket.assign(N+1, {}); parentIdx.assign(N+1, 0);
44
45	// Build predecessor lists and parent indices in DFS-number space
46	for (int u = 0; u < n; ++u) if (dfn[u]) {
47	for (int v : adj[u]) if (dfn[v]) {
48	pred[dfn[v]].push_back(dfn[u]);
49	}
50	}
51	for (int i = 1; i <= N; ++i) {
52	int u = rev[i];
53	semi[i] = label[i] = i;
54	if (i == 1) parentIdx[i] = 0; // root has no parent in DFS-indexed tree
55	else parentIdx[i] = dfn[parentOrig[u]];
56	}
57
58	// eval/link with path compression
59	auto compress = [&](auto&& self, int v) -> void {
60	if (ancestor[ancestor[v]] != 0) {
61	self(self, ancestor[v]);
62	if (semi[label[ancestor[v]]] < semi[label[v]]) label[v] = label[ancestor[v]];
63	ancestor[v] = ancestor[ancestor[v]];
64	}
65	};
66	auto eval = [&](auto&& self, int v) -> int {
67	if (ancestor[v] == 0) return label[v];
68	self(self, v);
69	return (semi[label[ancestor[v]]] < semi[label[v]]) ? label[ancestor[v]] : label[v];
70	};
71	auto link = [&](int u, int v){ ancestor[v] = u; };
72
73	// Main LT loop: compute semidominators and idoms (provisional)
74	for (int i = N; i >= 2; --i) {
75	for (int v : pred[i]) {
76	int u = eval(eval, v);
77	if (semi[i] > semi[u]) semi[i] = semi[u];
78	}
79	bucket[semi[i]].push_back(i);
80	link(parentIdx[i], i);
81	for (int w : bucket[parentIdx[i]]) {
82	int u = eval(eval, w);
83	idom[w] = (semi[u] < semi[w] ? u : parentIdx[i]);
84	}
85	bucket[parentIdx[i]].clear();
86	}
87	for (int i = 2; i <= N; ++i) {
88	if (idom[i] != semi[i]) idom[i] = idom[idom[i]];
89	}
90
91	// Build dominator tree in original indices
92	domTree.assign(n, {});
93	for (int i = 2; i <= N; ++i) {
94	int v = rev[i];
95	int p = rev[idom[i]];
96	domTree[p].push_back(v);
97	}
98	}
99	};
100
101	int main() {
102	ios::sync_with_stdio(false);
103	cin.tie(nullptr);
104
105	int n, m, r;
106	// Input: n m r, then m edges u v (0-based). r is the root.
107	if (!(cin >> n >> m >> r)) return 0;
108	DominatorTree DT(n);
109	for (int i = 0; i < m; ++i) {
110	int u, v; cin >> u >> v; DT.add_edge(u, v);
111	}
112	DT.build(r);
113
114	// Print immediate dominator of each node (original indices).
115	// Convention: idom[root] = root; unreachable -> -1
116	vector<int> idom_out(n, -1);
117	if (DT.dfn[r]) idom_out[r] = r;
118	for (int v = 0; v < n; ++v) if (DT.dfn[v] && v != r) {
119	int idx = DT.dfn[v];
120	int parent_idx = DT.idom[idx];
121	idom_out[v] = DT.rev[parent_idx];
122	}
123
124	for (int v = 0; v < n; ++v) cout << idom_out[v] << (v+1==n?'\n':' ');
125	return 0;
126	}
127