Guide to Competitive Programming

Another special class of directed graphs are successor graphs. In those graphs, the outdegree of each node is 1, i.e., each node has a unique successor. A successor graph consists of one or more components, each of which contains one cycle and some paths that lead to it.

successor graph Competitive programming

Successor graphs are sometimes called functional graphs, because any successor graph corresponds to a function succ(x) that defines the edges of the graph. The parameter x is a node of the graph, and the function gives the successor of the node.
For example, the function defines the graph.

Successor graphs, Competitive programming

Finding Successors:

Since each node of a successor graph has a unique successor, we can also define a function succ(x, k) that gives the node that we will reach if we begin at node x and walk k steps forward. For example, in our example graph succ(4, 6) = 2, because we will reach node 2 by walking 6 steps from node 4.

A straightforward way to calculate a value of succ(x, k) is to start at node x and walk k steps forward, which takes O(k) time. However, using preprocessing, any value of succ(x, k) can be calculated in only O(log k) time.

Let u denote the maximum number of steps we will ever walk. The idea is to precalculate all values of succ(x, k) where k is a power of two and at most u. This can be efficiently done, because we can use the following recurrence:

Finding Successors

The idea is that a path of length k that begins at node x can be divided into two paths of length k/2. Precalculating all values of succ(x, k) where k is a power of two and at most u takes O(n log u) time, because O(log u) values are calculated for each node. In our example graph, the first values are as follows:

cycle in successor graph

After the precalculation, any value of succ(x, k) can be calculated by presenting k as a sum of powers of two. Such a representation always consists of O(log k) parts, so calculating a value of succ(x, k) takes O(log k) time. For example, if we want to calculate the value of succ(x, 11), we use the formula succ(x, 11) = succ(succ(succ(x, 8), 2), 1).
In our example graph,

succ(4, 11) = succ(succ(succ(4, 8), 2), 1) = 5.

Cycle Detection:

Consider a successor graph that only contains a path that ends in a cycle. We may ask the following questions: if we begin our walk at the starting node, what is the first node in the cycle and how many nodes does the cycle contain? For example, we begin our walk at node 1, the first node that belongs to the cycle is node 4, and the cycle consists of three nodes (4, 5, and 6).

A simple way to detect the cycle is to walk in the graph and keep track of all nodes that have been visited. Once a node is visited for the second time, we can conclude that the node is the first node in the cycle.

This method works in O(n) time and also uses O(n) memory. However, there are better algorithms for cycle detection. The time complexity of such algorithms is still O(n), but they only use O(1) memory, which may be an important improvement if n is large.

One such algorithm is Floyd’s algorithm, which walks in the graph using two pointers a and b. Both pointers begin at the starting node x. Then, on each turn, the pointer a walks one step forward and the pointer b walks two steps forward. The process continues until the pointers meet each other:

a = succ(x);
b = succ(succ(x));
while (a != b) {
a = succ(a);
b = succ(succ(b));
}

At this point, the pointer a has walked k steps and the pointer b has walked 2k steps, so the length of the cycle divides k. Thus, the first node that belongs to the cycle can be found by moving the pointer a to node x and advancing the pointers step by step until they meet again.

a = x;
while (a != b) {
a = succ(a);
b = succ(b);
}
first = a;

After this, the length of the cycle can be calculated as follows:

b = succ(a);
length = 1;
while (a != b) {
b = succ(b);
length++;
}