Successor Graph

Successor graphs consist of nodes with an outdegree of 1.

Wait so a Successor Graph is basically a Linked List!!

Successor graph consists of one or more components, each of which contains one cycle and some paths that lead to it.

Precalculating Successor Paths

To compute the value $succ(x,k)$, we can find it faster in $O(\log k)$ instead of $O(k)$. We can use a similar idea of Binary Search and build the Table in $O(n\log u)$, and then co $succ(x,k)=\{\begin{array}{ll}succ(x)& k=1\\ succ(succ(x,k/2),k/2)& k>1\end{array}$

There is a similar idea used for Tree Query to find the $k$-th ancestor of a node in $O(\log k)$ time.

I don’t have the code.

Then, we can calculate for example: $succ(x,11)=succ(succ(succ(x,8),2),1)$