【题目】

【题意】给定n个数的置换，要求使n个点连成1棵树，满足u,v有边当且仅当a[u],a[v]有边，求一种方案或无解。n<=10^5。

【算法】数学 置换

【题解】置换可以分解成若干循环，那么两个点的连边本质上是两个循环之间的连边。

因为要求无环（树），易知所有循环长度必须为偶数（这里不包括最后的情况1）。

那么循环之间通过连边形成一棵树后，最后的问题是必须至少存在一个循环内部相互连边。（不可能通过循环之间的连边使得循环内部连边，否则循环之间的连边就会构成环）

即，至少存在一个循环的长度为1或2才能实现，其它所有循环都向这个中心循环连边就可以满足要求。

那么，有以下结论：

1.存在长度为1的循环，其它循环向其连边，得解。

2.存在长度为2的循环，且不存在>1的奇数长度的循环，其它循环向其连边（交替），得解。

3.否则，无解。

例如，(4,2,1,3)=>(1,2) (3,2) (4,2)　　(6,5,4,3,1,2)=>(1,3) (6,4) (2,3) (5, 4)

#include
      
       #include
       
        using namespace std;const int maxn=100010;int n,a[maxn],b[maxn];bool vis[maxn];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    int x=0,y;    for(int i=1;i<=n;i++)if(!vis[i]){        int j=i,len=0,h=0;        while(!vis[j]){            vis[j]=1;            len++;            b[j]=h;            h=1-h;            j=a[j];        }        if(len==1)x=1,y=i;else        if(len==2&&x!=-1&&x!=1)x=2,y=i;else        if(len%2==1&&x!=1)x=-1;    }    if(x<=0){printf("NO");return 0;}    if(x==1){        printf("YES\n");        for(int i=1;i<=n;i++)if(i!=y)printf("%d %d\n",i,y);    }    else{        printf("YES\n%d %d\n",y,a[y]);        for(int i=1;i<=n;i++)if(i!=y&&i!=a[y])printf("%d %d\n",i,b[i]?y:a[y]);    }    return 0;}