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, arr, \cdots, arr[n-1]$, such that the graph has the edge $(i, arr[i])$.
- $round\leftarrow 0$.
- 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.
- Loop $i$ from 0 to $n-1$:
If $first\_visited[i]$ is 0:
- Increase $round$ by 1.
- $index\leftarrow i$
- Loop the following as long as $first\_visited[index]$ is zero, i.e., $arr[index]$ is not visited.
- $first\_visited[index]\leftarrow round$
- $index \leftarrow arr[index]$
- 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.
On your algorithm
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.
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.