SPOJ 1421 - Goods（置換）

題意：一個1到n的排列，可以對兩個數字進行交換，每輪可進行多次交換，但是每個數字每輪只能交換一次，問幾輪才能把排列變成從1，2，3...，n的排列

思路：找出所有的循環節，長度為2的循環節只需要進行一次，剩下的則需要兩次

證明：長度為2的循環節只進行一次交換顯而易見，而剩下的可以拉成一條鏈的形式（將排列與1,2,3，...，n的排列連線），如果把這條鏈由兩頭向中間依次交換（即第i個與第k+1-i個進行交換），則會打破原來交叉的鏈，也就是分解了循環節，交叉的鏈最長為2，所以只需要兩次就OK了

 
#include <stdio.h>   
#include <string.h>   
#include <algorithm>   
using namespace std;  
  
int A[5010];  
int F[5010];  
int t[5010];  
int vis[5010];  
int ct,ans,d[5010][2];  
  
int dfs(int x)  
{  
    t[++ct]=A[x];  
    if(!vis[A[x]])  
    {  
        vis[A[x]]=1;  
        dfs(A[x]);  
    }  
}  
  
int check(int n)  
{  
    for(int i=1; i<=n; i++)  
    {  
        if(i!=A[i])return 0;  
    }  
    return 1;  
}  
  
int solve(int n)  
{  
    int f=0;  
    memset(vis,0,sizeof(vis));  
    for(int i=1; i<=n; i++)  
    {  
        if(!vis[i])  
        {  
            ct=0;  
            vis[i]=1;  
            dfs(i);  
            if(ct>2)f=1;  
            if(ct>=2)  
            {  
                for(int j=1; j<=ct/2; j++)  
                {  
                    d[ans][0]=t[j];  
                    d[ans][1]=t[ct+1-j];  
                    ans++;  
                    swap(A[F[t[j]]],A[F[t[ct+1-j]]]);  
                    swap(F[t[j]],F[t[ct+1-j]]);  
                }  
            }  
        }  
    }  
    if(!f)  
    return 0;  
    else  
    return 1;  
}  
  
int main()  
{  
    int n,f=0;  
    scanf("%d",&n);  
    for(int i=1; i<=n; i++)  
    {  
        scanf("%d",&A[i]);  
        F[A[i]]=i;  
    }  
    ans=0;  
    if(check(n))  
    {  
        printf("0\n");  
    }  
    else  
    {  
        if(!solve(n))  
        {  
            printf("1\n%d",ans);  
            for(int i=0;i<ans;i++)  
                printf(" %d-%d",d[i][0],d[i][1]);  
            printf("\n");  
        }  
        else  
        {  
            printf("2\n%d",ans);  
            for(int i=0;i<ans;i++)  
                printf(" %d-%d",d[i][0],d[i][1]);  
            printf("\n");  
            ans=0;  
            solve(n);  
            printf("%d",ans);  
            for(int i=0;i<ans;i++)  
                printf(" %d-%d",d[i][0],d[i][1]);  
            printf("\n");  
        }  
    }  
    return 0;  
}  

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int A[5010];
int F[5010];
int t[5010];
int vis[5010];
int ct,ans,d[5010][2];

int dfs(int x)
{
    t[++ct]=A[x];
    if(!vis[A[x]])
    {
        vis[A[x]]=1;
        dfs(A[x]);
    }
}

int check(int n)
{
    for(int i=1; i<=n; i++)
    {
        if(i!=A[i])return 0;
    }
    return 1;
}

int solve(int n)
{
    int f=0;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        if(!vis[i])
        {
            ct=0;
            vis[i]=1;
            dfs(i);
            if(ct>2)f=1;
            if(ct>=2)
            {
                for(int j=1; j<=ct/2; j++)
                {
                    d[ans][0]=t[j];
                    d[ans][1]=t[ct+1-j];
                    ans++;
                    swap(A[F[t[j]]],A[F[t[ct+1-j]]]);
                    swap(F[t[j]],F[t[ct+1-j]]);
                }
            }
        }
    }
    if(!f)
    return 0;
    else
    return 1;
}

int main()
{
    int n,f=0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&A[i]);
        F[A[i]]=i;
    }
    ans=0;
    if(check(n))
    {
        printf("0\n");
    }
    else
    {
        if(!solve(n))
        {
            printf("1\n%d",ans);
            for(int i=0;i<ans;i++)
                printf(" %d-%d",d[i][0],d[i][1]);
            printf("\n");
        }
        else
        {
            printf("2\n%d",ans);
            for(int i=0;i<ans;i++)
                printf(" %d-%d",d[i][0],d[i][1]);
            printf("\n");
            ans=0;
            solve(n);
            printf("%d",ans);
            for(int i=0;i<ans;i++)
                printf(" %d-%d",d[i][0],d[i][1]);
            printf("\n");
        }
    }
    return 0;
}