Parallel Sort

题意：给定长度为n的排列，一次操作你可以选择任意个下标数对：(x1,y1)，(x2,y2)，…(xn,yn)。
要求每个下标最多只出现一次。问最少需要几次操作能够将排列恢复为原排列，同时输出每次操作选择的下标。

思路：

之间连一条边，如果不形成环，那么一次操作就行，如果环上只有两个点，那么也只需要一次。
如果环中有个点,那么两次交换即可，只需要维护两个游标从首尾开始交换，把大环拆成若干个只有两个点的小环和若个排好序的点，然后再操作一次拆掉2个点的小环就行了。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=1e6+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[maxn];
bool vis[maxn];
vector<int>ans[2],tmp;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i)
        cin>>a[i];
    for(int i=1,now; i<=n; ++i) {
        if(vis[i]) continue;
        now=i;
        tmp.clear();
        tmp.emplace_back(now);
        vis[now]=1;
        while(!vis[a[now]]) {
            now=a[now];
            vis[now]=true;
            tmp.emplace_back(now);
        }
        for(int j=0,k=tmp.size()-1; j<k; ++j,--k) {
            ans[0].emplace_back(tmp[j]);
            ans[0].emplace_back(tmp[k]);
        }
        for(int j=1,k=tmp.size()-1; j<k; ++j,--k) {
            ans[1].emplace_back(tmp[j]);
            ans[1].emplace_back(tmp[k]);
        }
    }
    int cnt(0);
    for(int i=0; i<2; ++i)
        if(ans[i].size()) cnt=i+1;
        else break;
    cout<<cnt<<'\n';
    for(int i=0; i<cnt; ++i) {
        cout<<ans[i].size()/2<<' ';
        for(int k:ans[i]) cout<<k<<' ';
        cout<<'\n';
    }
    return 0;;
}