Find All Cycles

    1#include <bits/stdc++.h>
    2using namespace std;
    3#define int long long
    4vector<int> to;
    5vector<int> color, parent;
    6vector<vector<int>> cycles;
    7void dfs(int u){
    8    color[u] = 1; //visiting
    9    int v = to[u];
    10    if(color[v] == 0){ // unvisited 
    11        parent[v] = u;
    12        dfs(v);
    13    }else if(color[v] == 1){
    14        vector<int> cyc;
    15        int x = v;
    16        do {
    17            cyc.push_back(x);
    18            x = to[x];
    19        } while(x != v);
    20        int pos = min_element(cyc.begin(), cyc.end()) - cyc.begin();
    21        rotate(cyc.begin(), cyc.begin() + pos, cyc.end());
    22        cycles.push_back(move(cyc));
    23    }
    24    color[u] = 2; // done
    25}
    26signed main(){
    27    ios::sync_with_stdio(0); cin.tie(0);
    28    int n; cin >> n;
    29    to.assign(n + 1, 0);
    30    for(int i = 1; i <= n; i++){
    31        cin >> to[i];
    32    }
    33    color.assign(n + 1, 0);
    34    parent.assign(n + 1, -1);
    35    for(int i = 1; i <= n; i++){
    36        if(color[i] == 0) dfs(i);
    37    }
    38    sort(cycles.begin(), cycles.end());
    39    cout << cycles.size() << '\n';
    40    for(auto &c : cycles){
    41        for(int i = 0; i < c.size(); i++){
    42            cout << c[i] << (i == c.size() - 1 ? "\n" : " ");
    43        }
    44    }
    45    return 0;
    46}