Functional graphs

A **functional graph** has exactly one outgoing edge per vertex: next[v]. It has n vertices and n edges. Following next from any vertex must eventually repeat a vertex, so every component contains **exactly one cycle**, possibly a self-loop, and everything else is a tree whose edges point toward the cycle. The walk from a vertex looks like the Greek letter ρ: a tail, then a loop.

To find all cycle vertices in O(n) use a three-state walk. From each unvisited vertex, follow next, marking vertices as **on the current walk**. If the walk reaches a vertex already on the current walk, the walk has closed on itself and everything from that vertex around is a cycle. If it reaches a finished vertex, the walk was only a tail. Afterwards mark all vertices of the walk as finished.

Open the animation on the default array next = [1, 2, 0, 2, 3, 4, 6, 6]. Vertices 0, 1, 2 form a cycle of length 3; vertex 6 is a self-loop, a cycle of length 1; vertices 3, 4, 5 and 7 are tails. Floyd's tortoise and hare finds one cycle with O(1) extra memory, but the 3-state walk is the right tool when you need every cycle.

1static boolean[] onCycle(int[] next) {                                // next[v] = the single successor of v
2    int n = next.length;
3    int[] state = new int[n];                                         // 0 new, 1 on the current walk, 2 finished
4    boolean[] cyc = new boolean[n];
5    for (int s = 0; s < n; s++) {
6        int v = s;
7        while (state[v] == 0) { state[v] = 1; v = next[v]; }
8        if (state[v] == 1) {                                          // the walk closed on itself: v lies on a new cycle
9            for (int u = v; ; u = next[u]) { cyc[u] = true; if (next[u] == v) break; }
10        }
11        for (int u = s; state[u] == 1; u = next[u]) state[u] = 2;
12    }
13    return cyc;
14}

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}

Remove the cycle edges and what remains of each component is a set of **in-trees**: trees whose root is a cycle vertex and whose edges point toward the root. For every vertex we want two things: its **distance to the cycle** (the tail length) and its **entry**, the cycle vertex where it first lands.

Both are filled in one linear pass. Cycle vertices have distance 0 and are their own entries. For another vertex, walk next until a vertex with a known answer is reached, keeping the walk on a stack; then pop the stack and set dist[u] = dist[next[u]] + 1 and entry[u] = entry[next[u]]. Every vertex is pushed at most once, so the whole table costs O(n).

With the default array: vertex 3 goes to 2 (distance 1, entry 2), vertex 4 to 3 then 2 (distance 2, entry 2) and 5 has distance 3, all entering the cycle at 2. Vertex 7 goes to the self-loop 6 (distance 1, entry 6). These two arrays are the foundation of the distance queries below, and an in-tree is a perfect candidate for tree algorithms such as LCA (Chapter 42).

1// for each vertex: how many steps until it first lands on a cycle, and the cycle vertex where it lands
2static int[][] tails(int[] next, boolean[] onCycle) {
3    int n = next.length;
4    int[] dist = new int[n], entry = new int[n];
5    boolean[] done = new boolean[n];
6    for (int v = 0; v < n; v++) if (onCycle[v]) { done[v] = true; entry[v] = v; }
7    for (int s = 0; s < n; s++) {
8        Deque<Integer> path = new ArrayDeque<>();
9        int v = s;
10        while (!done[v]) { path.push(v); v = next[v]; }               // walk until a vertex whose answer is known
11        while (!path.isEmpty()) {                                     // then fill the answers backwards
12            int u = path.pop();
13            dist[u] = dist[next[u]] + 1;
14            entry[u] = entry[next[u]];
15            done[u] = true;
16        }
17    }
18    return new int[][]{dist, entry};
19}

How far does a vertex get after k steps when k is huge? Simulating costs O(k). **Binary lifting** precomputes up[j][v], the vertex reached after 2^j steps from v. Level 0 is next itself, and up[j][v] = up[j − 1][ up[j − 1][v] ]: two steps of length 2^(j−1). A table with ⌈log2 K⌉ levels handles every k below 2^levels.

Building the table is O(n log K) time and memory. The idea works because composing a function with itself is associative, which is why the same trick appears for ancestors in trees (Chapter 42) and for any “repeat an operation k times” query where one step can be combined with another.

Run the animation with the jump option. The preset “Jump 100 steps from vertex 5” walks 5 → 4 → 3 → 2 to reach the cycle after 3 steps, then goes round the 3-cycle for the remaining 97 steps, which is 32 full laps and 1 more step, ending at vertex 0.

1static int[][] jumpTable(int[] next, long maxSteps) {                 // up[j][v] = the vertex after 2^j steps from v
2    int n = next.length, levels = 1;
3    while ((1L << levels) <= maxSteps) levels++;
4    int[][] up = new int[levels][];
5    up[0] = next.clone();
6    for (int j = 1; j < levels; j++) {
7        up[j] = new int[n];
8        for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
9    }
10    return up;
11}

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}

With the jump table in hand, the vertex after k steps is found by reading the bits of k: for every set bit j, replace v by up[j][v]. A query costs O(log k), so the answer for k = 10^9 takes 30 table lookups.

There is an alternative that needs no table and uses the structure instead: simulate at most n steps (after which the walker is certainly on its cycle), then reduce the remaining steps modulo the cycle length. This costs O(n) per query but only O(n) memory, and it is the better choice when there are few queries. Binary lifting wins when there are many queries or when the function is not a plain successor (for example, when each step also carries a weight to be combined).

The Java method below requires k < 2^levels of the table built in the previous section. Check it against the simulation on small inputs before trusting it for large ones; the verification of this lesson did exactly that, with k up to one billion.

1static int kthSuccessor(int[][] up, int v, long k) {                  // needs k < 2^up.length
2    for (int j = 0; j < up.length; j++) if ((k >> j & 1) == 1) v = up[j][v];
3    return v;
4}

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}

**Distance query:** the smallest t ≥ 0 with next^t(u) = v, or “unreachable”. The answer depends on where v sits. If v is on a cycle, u first walks its tail (dist[u] steps) to its entry vertex, then travels around the cycle from the entry to v: (pos[v] − pos[entry[u]]) mod cycleLength more steps, provided both are on the same cycle. If v is on a tail, u must pass through it: it needs dist[u] ≥ dist[v], and the vertex reached after dist[u] − dist[v] steps must be v.

The class below precomputes the cycle positions, lengths and ids, and the tails from the previous sections in O(n). A query on a cycle target is O(1); a query on a tail target walks dist[u] − dist[v] steps (with binary lifting it becomes O(log n)).

The structure answers many questions: “do these two vertices collide?”, “after how many steps does the sequence repeat?” (tail length plus cycle length) and “what is the period?”. The verification compared every pair of vertices of thousands of random functions with direct simulation.

1// answers "how many steps from u until v?" in O(distance to v) after an O(n) setup
2static class Functional {
3    final int[] next, dist, entry, pos, cycleLen, cycleId;            // pos, cycleLen, cycleId: meaningful for cycle vertices
4    Functional(int[] next) {
5        this.next = next;
6        int n = next.length;
7        boolean[] onCycle = new boolean[n];
8        int[] state = new int[n];
9        for (int s = 0; s < n; s++) {                                 // find the cycles (3-colour walk)
10            int v = s;
11            while (state[v] == 0) { state[v] = 1; v = next[v]; }
12            if (state[v] == 1) for (int u = v; ; u = next[u]) { onCycle[u] = true; if (next[u] == v) break; }
13            for (int u = s; state[u] == 1; u = next[u]) state[u] = 2;
14        }
15        dist = new int[n]; entry = new int[n]; pos = new int[n]; cycleLen = new int[n]; cycleId = new int[n];
16        boolean[] done = new boolean[n];
17        for (int s = 0; s < n; s++) {                                 // number every cycle: position, length and an id
18            if (!onCycle[s] || done[s]) continue;
19            int len = 0;
20            for (int v = s; !done[v]; v = next[v]) { done[v] = true; pos[v] = len++; cycleId[v] = s; entry[v] = v; }
21            for (int v = s, i = 0; i < len; v = next[v], i++) cycleLen[v] = len;
22        }
23        for (int s = 0; s < n; s++) {                                 // tail length and landing vertex of every other vertex
24            Deque<Integer> path = new ArrayDeque<>();
25            int v = s;
26            while (!done[v]) { path.push(v); v = next[v]; }
27            while (!path.isEmpty()) { int u = path.pop(); dist[u] = dist[next[u]] + 1; entry[u] = entry[next[u]]; done[u] = true; }
28        }
29    }
30    int steps(int u, int v) {                                         // fewest steps from u to v, or -1
31        if (dist[v] == 0) {                                           // v is on a cycle: walk the tail, then round the cycle
32            int e = entry[u];
33            if (cycleId[e] != cycleId[v]) return -1;
34            return dist[u] + (pos[v] - pos[e] + cycleLen[v]) % cycleLen[v];
35        }
36        int gap = dist[u] - dist[v];                                  // v is on a tail: u must pass through it
37        if (gap < 0) return -1;
38        int x = u;
39        for (int i = 0; i < gap; i++) x = next[x];
40        return x == v ? gap : -1;
41    }
42}