This is a problem from CodeChef. Follow this link if you want to try this problem on your own.
Given a permutation of numbers from 1 to N. You can walk through the permutation to find cycles in it.
Here is how you can do it. Consider the permutation {3, 5, 2, 1, 4, 6}
Start with the first number at index 1, it contains 3.
Go to index 3, it contains 2.
Go to index 2, it contains 5.
Go to index 5, it contains 4.
Go to index 4, it contains 1.
Here we come back to index 1 again. This completes a cycle {1,3,2,5,4,1}
And if we start with 6, we end up there itself. This is a one element cycle {6,6}.
Similarly the permutation {3,2,1,5,4,6} contains 4 such cycles
1 3 1
2 2
4 5 4
6 6
The problem is given a permutation as input, you have to print the number of cycles and the cycles also.
To solve this problem we can maintain a visited array to store whether the element is already explored or not. Run a loop until you find a unvisited element, and start walking to find the cycle.
This is a purely an implementation challenge and does not need any algorithmic thinking.
This is a purely an implementation challenge and does not need any algorithmic thinking.
Here is the simple C++ implementation.