題目描述
As a master of parallel computing, schwer is recently considering about the method to achieve quick sorting on parallel computers. He needs your help!
Given a permutation ( p 1 , ⋯ , p n ) (p_1,\cdots,p_n) (p1,⋯,pn), you need to sort the permutation with minimum number of rounds. In a single round, one can take many pairs of integers ( x 1 , y 1 ) (x_1,y_1) (x1,y1), ⋯ \cdots ⋯, ( x k , y k ) (x_k,y_k) (xk,yk) as long as the values of x 1 x_1 x1, y 1 y_1 y1, ⋯ \cdots ⋯, x k , y k x_k,y_k xk,yk are pairwise distinct. Then with the help of k k k CPUs, for each i ∈ [ 1 , k ] i\in [1,k] i∈[1,k], the value of p x i p_{x_i} pxi and p y i p_{y_i} pyi will be switched immediately. Note that a permutation ( p 1 , ⋯ , p n ) (p_1,\cdots,p_n) (p1,⋯,pn) is sorted if for every integer i ∈ [ 1 , n ] i\in [1,n] i∈[1,n], p i = i p_i=i pi=i holds.
Take some examples. Assume that n = 4 n=4 n=4. For p = ( 1 , 2 , 3 , 4 ) p=(1,2,3,4) p=(1,2,3,4), the minimum number of round is 00 as it is already sorted. For p = ( 4 , 3 , 2 , 1 ) p=(4,3,2,1) p=(4,3,2,1), the answer is 1 1 1, as you can swap the indices ( 1 , 4 ) (1,4) (1,4) and ( 2 , 3 ) (2,3) (2,3) simultaneously.
輸入描述:
he first line of input contains a single integer n n n ( 1 ≤ n ≤ 1 0 5 ) (1\leq n\leq 10^5) (1≤n≤105), indicating the length of the permutation.
The second line contains n n n integers p 1 , . . . , p n ( 1 ≤ p i ≤ n ) p_1,...,p_n(1\leq p_i\leq n) p1,...,pn(1≤pi≤n), the given permutation. It is guaranteed that these integers form a permutation, that is, for every integer i ∈ [ 1 , n ] i\in [1,n] i∈[1,n] there exists an unique integer j ∈ [ 1 , n ] j\in [1,n] j∈[1,n] such that p j = i p_j=i pj=i.
輸出描述:
The first line of output should contain a single integer m m m, the minimum number of rounds to get the permutation sorted. Then print m m m line to show one possible solution.
The i i i-th of the next mm lines should describe the i i i-th round of your solution, beginning with a single integer k k k, and followed by 2 k 2k 2k integers x 1 , y 1 ⋯ x k , y k x_1,y_1 \cdots x_k,y_k x1,y1⋯xk,yk. The constraints that 1 ≤ x i , y i ≤ n 1\leq x_i,y_i\leq n 1≤xi,yi≤n and the 2 k 2k 2k integers are pairwise distinct must be held.
輸入
4
1 2 3 4
輸出
輸入
4
4 3 2 1
輸出
1
2 1 4 2 3
思路
最初想到是貪心，每次必定能使 n 2 \frac n2 2n 個數字排好序， l o g 2 n log_2n log2n 輪下來，能把所有數排序。并且使用一個隊列來記錄未排序，并且未在這一輪中交換過的數字。但是 l o g 2 n log_2n log2n 不是最少的回合數。
建構一張有向圖， n n n 個結點，每個結點有一條出邊和一條入邊，那麼這張圖就是由若幹個環組成。
- 一進制環需要 0 0 0 回合消掉環。
- 二進制環需要 1 1 1 回合消掉環。
- 多元環可以用一回合分解為若幹個二進制環（奇環還會拆分出一個一進制環），再用一回合消掉所有拆出來的環。
- 所有環之間獨立
是以，最多兩回合可以消掉所有環。
例如一個五元環：
首先交換 1 , 3 1,3 1,3，從五元環上拆分出一個二進制環：
五元環變為了三元環，并且 3 3 3 在這一輪中不能再次交換。那交換 5 , 4 5,4 5,4，又拆分出一個二進制環。
下一輪可以消掉所有的環。
代碼中， dfs \text{dfs} dfs 中的 fst \text{fst} fst 參數為 0 0 0 代表這是第一次進入 dfs \text{dfs} dfs ，環上所有點都未交換過。 fst \text{fst} fst 為 1 1 1 代表拆分後的環上有一個點已經交換過，在這一輪中不能再次交換。
fst \text{fst} fst 參數隻有在環為二進制環的時候才有用。因為對于一個二進制環，若所有點都未交換過，那麼應該在第一輪中就解開這個環；若換上有一個點已經交換過，那這個二進制環需要在第二輪中解開。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],p[N],vis[N];
vector<int> op[2];
void swp(int i, int j,int t){
op[t].push_back(i);
op[t].push_back(j);
swap(a[i],a[j]);
p[a[i]] = i; p[a[j]] = j;
vis[i]=vis[j]=1;
}
void dfs(int i,int fst){
if(a[i]==i) return;
if(a[a[i]]==i) return swp(i,a[i],fst);
int x=a[i],y=a[x],pre=p[i];
swp(i,y,0); swp(y,x,1); dfs(pre,1);
}
int main(){
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],p[a[i]] = i;
for(int i=1;i<=n;i++) if(!vis[i]&&a[i]!=i) dfs(i,0);
int ans=(op[0].size()>0)+(op[1].size()>0);
cout<<ans<<"\n";
for(int i=0;i<ans;i++){
cout<<op[i].size()/2;
for(int j=0;j<(int)op[i].size();j++)
cout<<" "<<op[i][j];
cout<<"\n";
}
}