PK

PKBytes

Explore tracks
Chapter 37: Graph Dynamic Programming and DAG Applications
37.05Intermediate / Advanced4 topics15 min4 interactive animations

Functional graph DP

A functional graph gives every vertex exactly one outgoing arrow: each component is one cycle with trees leading into it, and cycle detection, distance to the cycle and k-th successor queries follow from that shape.

Learning goals

  • Recognise a functional graph and describe its components
  • Find all cycles and the distance of each vertex to its cycle
  • Build jump pointers to find the k-th successor in O(log k)
  • Use cycle arithmetic when k is huge

Prerequisites

Directed graph fundamentalsBinary representation

Repeatedly applying a function, such as 'go to the next student in the chain' or 'the next state of a machine', is a walk in a graph where every vertex has exactly one outgoing arrow. Because of that single choice, the structure is very regular.

37.05.2

Cycles with in-trees

Every weakly connected component of a functional graph has **exactly one cycle** (possibly a self-loop), and trees whose arrows point towards the cycle, called *in-trees*. To find the cycles, walk from each unvisited vertex marking the current walk; if the walk meets a vertex of the current walk, that part is a new cycle; if it meets a finished vertex, the walk only added a tail.

Every vertex is walked once, so the total cost is O(n). The animation draws vertices on a cycle in green and shows the walk in progress; the second preset has one cycle through all vertices, the third has self-loops.

Java
1static List<List<Integer>> cycles(int[] next) {                    // every cycle, each listed in order along the arrows
2    int n = next.length;
3    int[] state = new int[n];                                      // 0 new, 1 on the current walk, 2 finished
4    List<List<Integer>> found = new ArrayList<>();
5    for (int s = 0; s < n; s++) {
6        if (state[s] != 0) continue;
7        List<Integer> walk = new ArrayList<>();
8        int v = s;
9        while (state[v] == 0) { state[v] = 1; walk.add(v); v = next[v]; }
10        if (state[v] == 1) found.add(new ArrayList<>(walk.subList(walk.indexOf(v), walk.size())));   // the walk met itself
11        for (int u : walk) state[u] = 2;
12    }
13    return found;
14}

Functional graphs: one successor per vertex, cycles with trees, jump pointers

Interactive · edit the input

Your input

Try

directed graph · 8 vertices · 8 edges

0
1
2
3
4
5
6
7
Vertex being walkedOn the current walkOn a cycleQuery vertex

steps to reach a cycle

-0
-1
-2
-3
-4
-5
-6
-7
Setup

Every vertex has exactly one outgoing arrow, so walking from any vertex either reaches a vertex seen before. Each connected piece is one cycle with trees hanging into it.

Step 1 / 22
Java
1static int[] stepsToCycle(int[] next) {          // 0 for vertices on a cycle
2    int n = next.length;
3    int[] state = new int[n], dist = new int[n];   // state: 0 new, 1 on the current walk, 2 finished
4    for (int s = 0; s < n; s++) {
5        if (state[s] != 0) continue;
6        List<Integer> walk = new ArrayList<>();
7        int v = s;
8        while (state[v] == 0) { state[v] = 1; walk.add(v); v = next[v]; }
9        int from = walk.size();                    // answers are filled backwards from here
10        if (state[v] == 1) {                       // the walk met itself: a new cycle
11            int at = walk.indexOf(v);
12            for (int i = at; i < walk.size(); i++) dist[walk.get(i)] = 0;
13            from = at;
14        }
15        for (int i = from - 1; i >= 0; i--) dist[walk.get(i)] = dist[next[walk.get(i)]] + 1;
16        for (int u : walk) state[u] = 2;
17    }
18    return dist;
19}
20static int[][] jumpTable(int[] next, int levels) {   // up[j][v] = the vertex reached after 2^j steps
21    int n = next.length;
22    int[][] up = new int[levels][];
23    up[0] = next.clone();
24    for (int j = 1; j < levels; j++) {
25        up[j] = new int[n];
26        for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
27    }
28    return up;
29}
30static int kthSuccessor(int[][] up, int v, long k) {
31    for (int j = 0; j < up.length; j++) if ((k >> j & 1) == 1) v = up[j][v];
32    return v;
33}

Live state

0 vertices walked

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 22 steps
StepLineStateWhat happens
1L3n=8Every vertex has exactly one outgoing arrow, so walking from any vertex either reaches a vertex seen before. Each connected piece is one cycle with trees hanging into it.
2L8start=0 walk=[0]Walk from 0: mark 0, then follow its arrow to 1.
3L8start=0 walk=[0, 1]Walk from 0: mark 1, then follow its arrow to 2.
4L8start=0 walk=[0, 1, 2]Walk from 0: mark 2, then follow its arrow to 0.
5L11cycle=[0, 1, 2]The walk reached 0, which is on the current walk: the vertices [0, 1, 2] form a cycle of length 3. Their distance to the cycle is 0.
6L15distances=[0, 0, 0]No tail: every vertex of this walk is on the cycle.
7L8start=3 walk=[3]Walk from 3: mark 3, then follow its arrow to 2.
8L11met=2The walk reached 2, which was finished earlier: the new vertices lead into it.
9L15distances=[0, 0, 0, 1]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
10L8start=4 walk=[4]Walk from 4: mark 4, then follow its arrow to 3.
11L11met=3The walk reached 3, which was finished earlier: the new vertices lead into it.
12L15distances=[0, 0, 0, 1, 2]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
13L8start=5 walk=[5]Walk from 5: mark 5, then follow its arrow to 4.
14L11met=4The walk reached 4, which was finished earlier: the new vertices lead into it.
15L15distances=[0, 0, 0, 1, 2, 3]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
16L8start=6 walk=[6]Walk from 6: mark 6, then follow its arrow to 6.
17L11cycle=[6]The walk reached 6, which is on the current walk: the vertices [6] form a cycle of length 1. Their distance to the cycle is 0.
18L15distances=[0, 0, 0, 1, 2, 3, 0]No tail: every vertex of this walk is on the cycle.
19L8start=7 walk=[7]Walk from 7: mark 7, then follow its arrow to 6.
20L11met=6The walk reached 6, which was finished earlier: the new vertices lead into it.
21L15distances=[0, 0, 0, 1, 2, 3, 0, 1]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
22L18return=[0, 0, 0, 1, 2, 3, 0, 1] cycles=22 cycles found. Distances to the cycle: [0, 0, 0, 1, 2, 3, 0, 1] (0 = on a cycle). Each vertex is walked once: O(n).
37.05.3

Jump pointers

To find the k-th successor quickly, precompute up[j][v]: where v lands after 2^j steps. up[0] is next, and up[j][v] = up[j-1][up[j-1][v]], since two jumps of 2^(j-1) make one of 2^j. To jump k steps, write k in binary and apply the jump for each 1 bit.

Building costs O(n log k) and each query O(log k). The second option of the animation builds the table row by row and then applies the bits of k. This is the same binary lifting used for lowest common ancestors in trees.

Java
1static int[][] jumpTable(int[] next, int levels) {                 // up[j][v] = the vertex reached after 2^j steps
2    int n = next.length;
3    int[][] up = new int[levels][];
4    up[0] = next.clone();
5    for (int j = 1; j < levels; j++) {
6        up[j] = new int[n];
7        for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
8    }
9    return up;
10}
11static int kthSuccessor(int[][] up, int v, long k) {               // k must be below 2^levels
12    for (int j = 0; j < up.length; j++) if ((k >> j & 1) == 1) v = up[j][v];
13    return v;
14}

Functional graphs: one successor per vertex, cycles with trees, jump pointers

Interactive · edit the input

Your input

Try

directed graph · 8 vertices · 8 edges

0
1
2
3
4
5
6
7
Vertex being walkedOn the current walkOn a cycleQuery vertex

steps to reach a cycle

-0
-1
-2
-3
-4
-5
-6
-7
Setup

Every vertex has exactly one outgoing arrow, so walking from any vertex either reaches a vertex seen before. Each connected piece is one cycle with trees hanging into it.

Step 1 / 22
Java
1static int[] stepsToCycle(int[] next) {          // 0 for vertices on a cycle
2    int n = next.length;
3    int[] state = new int[n], dist = new int[n];   // state: 0 new, 1 on the current walk, 2 finished
4    for (int s = 0; s < n; s++) {
5        if (state[s] != 0) continue;
6        List<Integer> walk = new ArrayList<>();
7        int v = s;
8        while (state[v] == 0) { state[v] = 1; walk.add(v); v = next[v]; }
9        int from = walk.size();                    // answers are filled backwards from here
10        if (state[v] == 1) {                       // the walk met itself: a new cycle
11            int at = walk.indexOf(v);
12            for (int i = at; i < walk.size(); i++) dist[walk.get(i)] = 0;
13            from = at;
14        }
15        for (int i = from - 1; i >= 0; i--) dist[walk.get(i)] = dist[next[walk.get(i)]] + 1;
16        for (int u : walk) state[u] = 2;
17    }
18    return dist;
19}
20static int[][] jumpTable(int[] next, int levels) {   // up[j][v] = the vertex reached after 2^j steps
21    int n = next.length;
22    int[][] up = new int[levels][];
23    up[0] = next.clone();
24    for (int j = 1; j < levels; j++) {
25        up[j] = new int[n];
26        for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
27    }
28    return up;
29}
30static int kthSuccessor(int[][] up, int v, long k) {
31    for (int j = 0; j < up.length; j++) if ((k >> j & 1) == 1) v = up[j][v];
32    return v;
33}

Live state

0 vertices walked

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 22 steps
StepLineStateWhat happens
1L3n=8Every vertex has exactly one outgoing arrow, so walking from any vertex either reaches a vertex seen before. Each connected piece is one cycle with trees hanging into it.
2L8start=0 walk=[0]Walk from 0: mark 0, then follow its arrow to 1.
3L8start=0 walk=[0, 1]Walk from 0: mark 1, then follow its arrow to 2.
4L8start=0 walk=[0, 1, 2]Walk from 0: mark 2, then follow its arrow to 0.
5L11cycle=[0, 1, 2]The walk reached 0, which is on the current walk: the vertices [0, 1, 2] form a cycle of length 3. Their distance to the cycle is 0.
6L15distances=[0, 0, 0]No tail: every vertex of this walk is on the cycle.
7L8start=3 walk=[3]Walk from 3: mark 3, then follow its arrow to 2.
8L11met=2The walk reached 2, which was finished earlier: the new vertices lead into it.
9L15distances=[0, 0, 0, 1]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
10L8start=4 walk=[4]Walk from 4: mark 4, then follow its arrow to 3.
11L11met=3The walk reached 3, which was finished earlier: the new vertices lead into it.
12L15distances=[0, 0, 0, 1, 2]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
13L8start=5 walk=[5]Walk from 5: mark 5, then follow its arrow to 4.
14L11met=4The walk reached 4, which was finished earlier: the new vertices lead into it.
15L15distances=[0, 0, 0, 1, 2, 3]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
16L8start=6 walk=[6]Walk from 6: mark 6, then follow its arrow to 6.
17L11cycle=[6]The walk reached 6, which is on the current walk: the vertices [6] form a cycle of length 1. Their distance to the cycle is 0.
18L15distances=[0, 0, 0, 1, 2, 3, 0]No tail: every vertex of this walk is on the cycle.
19L8start=7 walk=[7]Walk from 7: mark 7, then follow its arrow to 6.
20L11met=6The walk reached 6, which was finished earlier: the new vertices lead into it.
21L15distances=[0, 0, 0, 1, 2, 3, 0, 1]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
22L18return=[0, 0, 0, 1, 2, 3, 0, 1] cycles=22 cycles found. Distances to the cycle: [0, 0, 0, 1, 2, 3, 0, 1] (0 = on a cycle). Each vertex is walked once: O(n).
37.05.4

Path length to cycle

The **distance to the cycle** of a vertex is the number of steps until the walk first lands on a cycle vertex: 0 on the cycle itself, and 1 + distance(next[v]) otherwise. Fill it in during the cycle search, backwards along each walk, so every vertex is computed once.

With the tail length and the cycle length, even a huge k is easy: after the t steps of the tail, the position repeats every c steps, so the k-th vertex of the walk is the vertex at index t + (k - t) mod c. This costs O(n) per query with no table.

Java
1static int[] stepsToCycle(int[] next) {                            // 0 for vertices on a cycle
2    int n = next.length;
3    int[] state = new int[n], dist = new int[n];                   // state: 0 new, 1 on the current walk, 2 finished
4    for (int s = 0; s < n; s++) {
5        if (state[s] != 0) continue;
6        List<Integer> walk = new ArrayList<>();
7        int v = s;
8        while (state[v] == 0) { state[v] = 1; walk.add(v); v = next[v]; }
9        int from = walk.size();                                    // answers are filled backwards from here
10        if (state[v] == 1) {                                       // the walk met itself: a new cycle
11            int at = walk.indexOf(v);
12            for (int i = at; i < walk.size(); i++) dist[walk.get(i)] = 0;
13            from = at;
14        }
15        for (int i = from - 1; i >= 0; i--) dist[walk.get(i)] = dist[next[walk.get(i)]] + 1;
16        for (int u : walk) state[u] = 2;
17    }
18    return dist;
19}
20static int kthByCycleMath(int[] next, int v, long k) {             // O(n) per query, no table
21    int n = next.length;
22    int[] firstSeen = new int[n];
23    Arrays.fill(firstSeen, -1);
24    List<Integer> path = new ArrayList<>();
25    int x = v;
26    while (firstSeen[x] == -1) { firstSeen[x] = path.size(); path.add(x); x = next[x]; }
27    int tail = firstSeen[x], cycle = path.size() - tail;           // x is the first vertex seen twice
28    if (k < path.size()) return path.get((int) k);
29    return path.get(tail + (int) ((k - tail) % cycle));
30}

Functional graphs: one successor per vertex, cycles with trees, jump pointers

Interactive · edit the input

Your input

Try

directed graph · 8 vertices · 8 edges

0
1
2
3
4
5
6
7
Vertex being walkedOn the current walkOn a cycleQuery vertex

steps to reach a cycle

-0
-1
-2
-3
-4
-5
-6
-7
Setup

Every vertex has exactly one outgoing arrow, so walking from any vertex either reaches a vertex seen before. Each connected piece is one cycle with trees hanging into it.

Step 1 / 22
Java
1static int[] stepsToCycle(int[] next) {          // 0 for vertices on a cycle
2    int n = next.length;
3    int[] state = new int[n], dist = new int[n];   // state: 0 new, 1 on the current walk, 2 finished
4    for (int s = 0; s < n; s++) {
5        if (state[s] != 0) continue;
6        List<Integer> walk = new ArrayList<>();
7        int v = s;
8        while (state[v] == 0) { state[v] = 1; walk.add(v); v = next[v]; }
9        int from = walk.size();                    // answers are filled backwards from here
10        if (state[v] == 1) {                       // the walk met itself: a new cycle
11            int at = walk.indexOf(v);
12            for (int i = at; i < walk.size(); i++) dist[walk.get(i)] = 0;
13            from = at;
14        }
15        for (int i = from - 1; i >= 0; i--) dist[walk.get(i)] = dist[next[walk.get(i)]] + 1;
16        for (int u : walk) state[u] = 2;
17    }
18    return dist;
19}
20static int[][] jumpTable(int[] next, int levels) {   // up[j][v] = the vertex reached after 2^j steps
21    int n = next.length;
22    int[][] up = new int[levels][];
23    up[0] = next.clone();
24    for (int j = 1; j < levels; j++) {
25        up[j] = new int[n];
26        for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
27    }
28    return up;
29}
30static int kthSuccessor(int[][] up, int v, long k) {
31    for (int j = 0; j < up.length; j++) if ((k >> j & 1) == 1) v = up[j][v];
32    return v;
33}

Live state

0 vertices walked

n

8

No condition evaluated on this step
Execution trace (dry run table)Show 22 steps
StepLineStateWhat happens
1L3n=8Every vertex has exactly one outgoing arrow, so walking from any vertex either reaches a vertex seen before. Each connected piece is one cycle with trees hanging into it.
2L8start=0 walk=[0]Walk from 0: mark 0, then follow its arrow to 1.
3L8start=0 walk=[0, 1]Walk from 0: mark 1, then follow its arrow to 2.
4L8start=0 walk=[0, 1, 2]Walk from 0: mark 2, then follow its arrow to 0.
5L11cycle=[0, 1, 2]The walk reached 0, which is on the current walk: the vertices [0, 1, 2] form a cycle of length 3. Their distance to the cycle is 0.
6L15distances=[0, 0, 0]No tail: every vertex of this walk is on the cycle.
7L8start=3 walk=[3]Walk from 3: mark 3, then follow its arrow to 2.
8L11met=2The walk reached 2, which was finished earlier: the new vertices lead into it.
9L15distances=[0, 0, 0, 1]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
10L8start=4 walk=[4]Walk from 4: mark 4, then follow its arrow to 3.
11L11met=3The walk reached 3, which was finished earlier: the new vertices lead into it.
12L15distances=[0, 0, 0, 1, 2]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
13L8start=5 walk=[5]Walk from 5: mark 5, then follow its arrow to 4.
14L11met=4The walk reached 4, which was finished earlier: the new vertices lead into it.
15L15distances=[0, 0, 0, 1, 2, 3]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
16L8start=6 walk=[6]Walk from 6: mark 6, then follow its arrow to 6.
17L11cycle=[6]The walk reached 6, which is on the current walk: the vertices [6] form a cycle of length 1. Their distance to the cycle is 0.
18L15distances=[0, 0, 0, 1, 2, 3, 0]No tail: every vertex of this walk is on the cycle.
19L8start=7 walk=[7]Walk from 7: mark 7, then follow its arrow to 6.
20L11met=6The walk reached 6, which was finished earlier: the new vertices lead into it.
21L15distances=[0, 0, 0, 1, 2, 3, 0, 1]Fill the tail backwards: each tail vertex is one step further from the cycle than its successor.
22L18return=[0, 0, 0, 1, 2, 3, 0, 1] cycles=22 cycles found. Distances to the cycle: [0, 0, 0, 1, 2, 3, 0, 1] (0 = on a cycle). Each vertex is walked once: O(n).

Practice ladder

Now try it yourself

Easy

  • Linked List Cycle

Medium

  • Linked List Cycle II
  • Find the Duplicate Number
  • Longest Cycle in a Graph

Advanced

  • Maximum Employees to Be Invited to a Meeting
  • Count Visited Nodes in a Directed Graph
  • Kth Ancestor of a Tree Node

Key takeaways

  • A functional graph has one outgoing arrow per vertex; each component is a cycle with trees pointing into it.
  • Find cycles by walking and marking; every vertex is walked once, O(n).
  • Binary lifting: up[j][v] after 2^j steps; k-th successor in O(log k).
  • With the tail and cycle lengths, the k-th vertex is at index tail + (k - tail) mod cycle for large k.