Prerequisite:- None
Problem:- Given a permutation of an integer n, walk around the permutation to print the number of cycles present and print the pattern of each cycle.
To find the cycles :-
Take a permutation 2 4 5 1 7 6 3 8
Find the number of cycles present in the permutations and print the cycles as well.
Start from the first position, you find 2 there, so move to the second position.
4 is present in the second position, so move to the 4th position.
1 is present in the fourth position, so you’ve reached back to the first position and one cycle gets completed.
Now, again move to the leftmost unvisited position this time you will reach to 3rd position and go through 3 5 7 3
Keep on visiting the leftmost unvisited until you visit the whole array
You resultant output will be:
4
1 2 4 1
3 5 7 3
6 6
8 8
Explanation :- Find each cycle one by one and add them to a 2D vector until we iterate over each element of the array.
Algorithm :-
Keep a pointer on the leftmost unvisited element of the array.
Create an array to mark visited and unvisited positions of the array.
Start from the left pointer, initially pointing to the first position. Mark the position as visited and then move to the next position through the element present in the first position, and keep moving until you reach back to the first position and the cycle is completed.
Store the cycle.
Increase the left pointer. Check if the position is visited or not. If visited, continue increasing the left pointer; if unvisited, follow the previous steps and continue visiting the positions.
C++ Solution :-
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
vector<int>v1(n);
vector<bool>check(n+1,true);
for(int i=0;i<n;i++){
cin>>v1[i];
}
int start = 1;
vector<vector<int>>ans;
while(start!=n+1){
if(check[start-1]==false){
start++;
continue;
}
int pos = start;
vector<int>v2;
while(check[pos-1]==true){
check[pos-1] = false;
v2.push_back(pos);
pos = v1[pos-1];
}
v2.push_back(pos);
ans.push_back(v2);
// cout<<"\n";
}
cout<<ans.size()<<"\n";
for(auto e:ans){
for(auto f:e){
cout<<f<<" ";
}
cout<<"\n";
}
// your code goes here
}