Other/CyclePartition.hpp

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Other/CyclePartition.hpp"

Verified with

• test/yuki5125.test.cpp

Code

// 0-indexed parmutation only
vector<vector<int>> cycle_partition(const vector<int> &p){
    int n=p.size();
    vector<vector<int>> ret;
    vector<bool> check(n,false);
    rep(i,n)if(!check[p[i]]){
        vector<int> v;
        int pos=p[i];
        v.push_back(i);
        check[i]=true;
        while(pos!=i){
            v.push_back(pos);
            check[pos]=true;
            pos=p[pos];
        }
        ret.push_back(v);
    }
    return ret;
}

#line 1 "Other/CyclePartition.hpp"
// 0-indexed parmutation only
vector<vector<int>> cycle_partition(const vector<int> &p){
    int n=p.size();
    vector<vector<int>> ret;
    vector<bool> check(n,false);
    rep(i,n)if(!check[p[i]]){
        vector<int> v;
        int pos=p[i];
        v.push_back(i);
        check[i]=true;
        while(pos!=i){
            v.push_back(pos);
            check[pos]=true;
            pos=p[pos];
        }
        ret.push_back(v);
    }
    return ret;
}

Back to top page