Permutation cycles - CodeChef

Problem solving with programming: Permutation cycles - Code chef problem
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.

 cin >> n;


 vector<int> perm(n);


 int i;


 for( i = 0; i < n; i++ )


 {


  cin >> perm[i];


 }


 int cycleCount = 0;


 vector<bool> visited(n,false);


 vector< vector<int> > cycles;


 


 for( i = 0; i < n; i++ )


 {


  


  if( !visited[i] )


  {


   vector<int> cycle;


   cycleCount++;


   cycle.push_back(i);


   int next = perm[i]-1;


   while ( true )


   {


    cycle.push_back(next);


    visited[next] = true;


    if( next == i )


     break;


    next = perm[next]-1;


   }


   cycles.push_back(cycle);


  }


  


 }


 cout << cycleCount << endl;


 for( i = 0; i < cycles.size(); i++ )


 {


  for( int j = 0; j < cycles[i].size(); j++ )


   cout << cycles[i][j]+1 << " ";


  cout << endl;


 }

Read full article from Problem solving with programming: Permutation cycles - Code chef problem