go-lengauer-tarjan-immediate-dominators-cfg
Done. The deliverable is ~/go-lengauer-tarjan-immediate-dominators-cfg.md — a self-contained markdown with the title, root-cause analysis, the exact Go fix, and verification.
Environment: The toolchain is Google Go (golang) 1.26 — classic paren-free syntax (for i := 0; i < n; i++, for {} + break instead of while, make([]int, n), append, len, io.ReadAll, os.Stdout.Write).
Root cause: At N=200000/M=500000 both naive strategies TLE: - iterative bit-vector dominator dataflow needs Θ(N) fixpoint rounds → Θ(N·(N+M)) ≈ 10¹¹ ops; - O(N·M) reachability brute force is the same order; - plus, recursive DFS or recursive LT path compression overflows the stack on the 200k deep-chain family.
Fix: Lengauer–Tarjan semi-NCA with an explicit link-eval forest (iterative DFS numbering, reverse-dfn semi-dominator pass with eval/link, bucketed NCA idom assignment, final correction pass). Entirely iterative; O((N+M)·α(N)) time, O(N+M) memory. Unreachable → -1, idom[0] = 0, self-/multi-edges handled.
Verification performed:
- 470+ randomized + structured small cases vs an O(N·M) reachability brute force (brute.go, also included in the doc): byte-identical outputs, including the classic semi ≠ idom correction case (0,2,0 for 0→1,0→2,2→1) and unreachable/isolated/self-loop edge cases;
- medium graphs up to n=1500 vs brute: pass;
- deep chain N=200000: exact expected output (0,0,1,…,199999);
- timing at full scale (Go 1.26): chain 56 ms, random-graph M=500k 304 ms, layered DAG 128 ms.
To use it: extract the two code blocks (sol.go, brute.go) and run go run sol.go < graph.in.
# Evidence - Problem class: go-lengauer-tarjan-immediate-dominators-cfg - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T10:17:52.871Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Write a Go program (standard library only: bufio/os/fmt) that reads a directed graph and prints the immediate dominator of every vertex using the Lengauer-Tarjan algorithm (semi-NCA or full LT with link-eval); naive iterative bit-vector dataflow will TLE on the worst-case families. Input: first line N M (1 <= N <= 200000, 0 <= M <= 500000), then M lines u v (0-indexed); vertex 0 is the unique entry and some vertices may be unreachable from it. For each i in 0..N-1 print idom[i] on its own line, where idom[0] = 0, unreachable vertices get -1, and idom[i] is the unique strict dominator of i that is dominated by every other strict dominator of i; verify against an O(N*M) reachability brute force on random small graphs and deep chain graphs.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lengauer-tarjan-immediate-dominators-cfg", "provider": "openrouter", "solved_at": "2026-09-05T10:17:52.871Z", "version": "1.26"}Done. The deliverable is ~/go-lengauer-tarjan-immediate-dominators-cfg.md — a self-contained markdown with the title, root-cause analysis, the exact Go fix, and verification.
Environment: The toolchain is Google Go (golang) 1.26 — classic paren-free syntax (for i := 0; i < n; i++, for {} + break instead of while, make([]int, n), append, len, io.ReadAll, os.Stdout.Write).
Root cause: At N=200000/M=500000 both naive strategies TLE: - iterative bit-vector dominator dataflow needs Θ(N) fixpoint rounds → Θ(N·(N+M)) ≈ 10¹¹ ops; - O(N·M) reachability brute force is the same order; - plus, recursive DFS or recursive LT path compression overflows the stack on the 200k deep-chain family.
Fix: Lengauer–Tarjan semi-NCA with an explicit link-eval forest (iterative DFS numbering, reverse-dfn semi-dominator pass with eval/link, bucketed NCA idom assignment, final correction pass). Entirely iterative; O((N+M)·α(N)) time, O(N+M) memory. Unreachable → -1, idom[0] = 0, self-/multi-edges handled.
Verification performed:
- 470+ randomized + structured small cases vs an O(N·M) reachability brute force (brute.go, also included in the doc): byte-identical outputs, including the classic semi ≠ idom correction case (0,2,0 for 0→1,0→2,2→1) and unreachable/isolated/self-loop edge cases;
- medium graphs up to n=1500 vs brute: pass;
- deep chain N=200000: exact expected output (0,0,1,…,199999);
- timing at full scale (Go 1.26): chain 56 ms, random-graph M=500k 304 ms, layered DAG 128 ms.
To use it: extract the two code blocks (sol.go, brute.go) and run go run sol.go < graph.in.
# Evidence - Problem class: go-lengauer-tarjan-immediate-dominators-cfg - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T10:17:52.871Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Write a Go program (standard library only: bufio/os/fmt) that reads a directed graph and prints the immediate dominator of every vertex using the Lengauer-Tarjan algorithm (semi-NCA or full LT with link-eval); naive iterative bit-vector dataflow will TLE on the worst-case families. Input: first line N M (1 <= N <= 200000, 0 <= M <= 500000), then M lines u v (0-indexed); vertex 0 is the unique entry and some vertices may be unreachable from it. For each i in 0..N-1 print idom[i] on its own line, where idom[0] = 0, unreachable vertices get -1, and idom[i] is the unique strict dominator of i that is dominated by every other strict dominator of i; verify against an O(N*M) reachability brute force on random small graphs and deep chain graphs.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lengauer-tarjan-immediate-dominators-cfg", "provider": "openrouter", "solved_at": "2026-09-05T10:17:52.871Z", "version": "1.26"}