SPOJ 1421 - Goods（置换）

题意：一个1到n的排列，可以对两个数字进行交换，每轮可进行多次交换，但是每个数字每轮只能交换一次，问几轮才能把排列变成从1，2，3...，n的排列

思路：找出所有的循环节，长度为2的循环节只需要进行一次，剩下的则需要两次

证明：长度为2的循环节只进行一次交换显而易见，而剩下的可以拉成一条链的形式（将排列与1,2,3，...，n的排列连线），如果把这条链由两头向中间依次交换（即第i个与第k+1-i个进行交换），则会打破原来交叉的链，也就是分解了循环节，交叉的链最长为2，所以只需要两次就OK了

 
#include    
#include    
#include    
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
#include 
#include 
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