Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge

Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles, which we call the branches. Describe a linear time algorithm that identifies all of the cycles and computes the length of each cycle. You can assume that the input is given as an array A, where A[i] is the neighbor of i, so that the graph has the edge (i, A[i]).

I kind of have an idea of how to approach the algorithm but have no idea what to do with the proof of my algorithm. So far I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex.

Edit: what I ended up writing

For all element i of A:
If i has not been visited (not in the map)
Store the index i as key and order of traversal as value in a map
Add i to an array
Get A[i] as neighbor j
While j is not in the map (not visited)
Store the j as key and order of traversal as value in a map
Add j to an array
j’s neighbor becomes j
Endwhile
If resulting index j is not already part of a confirmed cycle
Store array into confirmed cycle set
Get j’s order of traversal of from map as o
Output length of cycle by deducting o from array length
Output part of the array that is the solution
Store array from index array.size() - o to the end into solution set
Endif
Endif
Endfor

• Do you have a concrete algorithm in mind? Commented Jan 30, 2020 at 5:36
• @YuvalFilmus I ended up writing something like what's in the edited code chunk, but it is probably very wrong because that's just the way with pseudocode. Commented Jan 31, 2020 at 7:53
• Have you tried something like Floyd’s linked list cycle detection algorithm? Commented Jan 31, 2020 at 20:01
• @JohnL. Yes, it is very helpful! Sorry I forgot to accept the answer. Commented Feb 4, 2020 at 11:42

Unfortunately, your algorithm is not correct.

Let us call a directed graph where each vertex has exactly one outgoing edge a unique-outgoing graph.

What does a unique-outgoing graph look like?

It consists of some directed tree and some directed cycles, all of which are disjoint except that every root of the trees is also a vertex of some cycle. Or, it looks like a collection of directed cycles with some directed trees attached to them.

Here is an illustration, which corresponds to the array $$[5, 12, 3, 10, 9, 2, 3, 14, 14, 7, 2, 14, 5, 11, 4]$$. There are two connected components in that graph. One component has the cycle of vertices 2, 3, 10 with two attached trees, the tree with vertices 2, 5, 0, 12, 1 and the tree with vertices 3, 6. The other component has the cycle of vertices 4, 9, 7, 14 with one attached tree, which has vertices 14, 8, 11, 13.

A simple algorithm

Here is the pseudocode, which is about as simple as possible.

Input: Array $$arr[0], arr[1], \cdots, arr[n-1]$$, such that the graph has the edge $$(i, arr[i])$$.

Procedure:

1. $$round\leftarrow 0$$.
2. Create array $$first\_visited$$ of $$n$$ zeros, where $$first\_visited[i]$$ will record the round at which $$arr[i]$$ is first visited. No element is visited at round 0.
3. Loop $$i$$ from 0 to $$n-1$$:
If $$first\_visited[i]$$ is 0:
1. Increase $$round$$ by 1.
2. $$index\leftarrow i$$
3. Loop the following as long as $$first\_visited[index]$$ is zero, i.e., $$arr[index]$$ is not visited.
1. $$first\_visited[index]\leftarrow round$$
2. $$index \leftarrow arr[index]$$
4. Now $$first\_visited[index]$$ must be non-zero.
If $$first\_visited[index]$$ is equal to $$round$$, a new cycle has been found! Record (or output) the cycle as well as its length by chasing the elements starting from $$index$$. Otherwise, do nothing.

When we run the algorithm on the aforementioned array, we will visit

• 0, 5, 2, 3, 10, 2 in round 1. The cycle 2, 3, 10 of length 3 will be recorded.

• 1, 12, 5 in round 2.

• 4, 9, 7, 14, 4 in round 3. The cycle 4, 9, 7, 14 of length 4 will be recorded.

• 6, 3 in round 4.

• 8, 14 in round 5.

• 11, 14 in round 6.

• 13, 11 in round 7.

Basically, the algorithm loops over all elements from index 0 to $$n-1$$. From each unvisited element, it makes an inner loop where it chases the next element via its outgoing edge, until it reaches a visited element. Each inner loop constitutes a round of chasing, during which each newly-visited element will be associated with the number of rounds happened so far.

The algorithm runs in $$O(n)$$ time with $$O(n)$$ space.

I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex

You have got the basic idea. However, a new cycle might not be found when a vertex points back to a vertex that has been traversed, even if it is not part of any confirmed cycles. For example, consider the moment when your algorithm have visited 0, 5, 2, 3, 10, 2, 1, 12 and then 5 again. Vertex 5, although revisited, is not part of any cycle.

To ensure that a new cycle will be found when you revisited a vertex, the first visit to that revisited vertex must happen after the visit to the vertex i in your algorithm. That is why the variable $$round$$ is introduced in the above algorithm, which is, in fact, the only critical difference between the two algorithms.

Exercises

Here are a couple of exercises that help prove the above algorithm is correct.

Exercise 1. Show that there is exactly one cycle in each connected component.

Exercise 2. Prove the following invariant of the above algorithm. At the start of step 3.1, all visited vertices and edges so far form a unique-outgoing graph.

• Here is another way to characterize a connected uniq-outgoing graph: it is a rooted directed tree with all its edges pointing towards the root and an extra edge from the root to an existing vertex Commented Feb 1, 2020 at 17:27