SuccessorGraph.md (1051B)
1 # Successor Graph 2 3 **Source:** Competitive Programmer's Handbook Ch 16 4 5 **Definition:** A successor graph is a directed graph where the out-degree of every node is exactly 1. 6 7 ## Implication 8 9 Since each node has an out-degree of 1, a successor graph with $n$ vertices has $n$ edges. This means the graph must have at least one cycle. Specifically, successor graphs must have one cycle per connected component. 10 11 Since each vertex has one edge, there's a function $f: V \to V$ where V is the set of all vertices, and $f(v_i) = v_j$ where $v_j$ is the successor to $v_i$. For this reason, successor graphs are sometimes called functional graphs. 12 13 Additionally, we may also define a function $s: V \times \mathbb{N} \to V$ such that $s(v_i,k)$ is the vertex that will be reached from $v_i$ after walking $k$ steps forwards. 14 15 This successor function may be naively evaluated by performing a walk, with a worst case asymptotic time complexity of $O(k)$, but a better approach that involves pre-processing is in the complexity class of $O(\text{log}(n))$.