# 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(gk)$ instead of $O(k)$. We can use a similar idea of Binary Search and build the Table in $O(ngu)$, and then co $succ(x,k)={succ(x)succ(succ(x,k/2),k/2) k=1k>1 $

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

I don’t have the code.

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