"洛谷題目頁面傳送門" & "CodeForces題目頁面傳送門" 定義一個$1\sim n$的排列$a$的平方$a^2=b$，當且僅當$\forall i\in[1,n],b_i=a_{a_i}$，即$a^2$為將$a$在$[1,2,\cdots,n]$上映射$2$次所得的排列。現在給定一個$1\ ...
洛谷題目頁面傳送門 & CodeForces題目頁面傳送門
定義一個\(1\sim n\)的排列\(a\)的平方\(a^2=b\)，當且僅當\(\forall i\in[1,n],b_i=a_{a_i}\)，即\(a^2\)為將\(a\)在\([1,2,\cdots,n]\)上映射\(2\)次所得的排列。現在給定一個\(1\sim n\)的排列\(a\)，求\(b\)使得\(b^2=a\)，即求\(a\)的平方根。若有多解，輸出任意一個。若無解，輸出\(-1\)。
\(n\le10^6\)。
看到關於映射的題目，首先想到轉化為圖論。\(\forall i\in[1,n]\)，從\(i\)到\(a_i\)建一條有向邊，得到一張有向圖\(G=(V=[1,n],E=\{(x,y)\mid a_x=y\})\)。很顯然，對於一個排列建出的圖一定是由若幹個環組成的，因為每個節點的入度、出度均為\(1\)。那麼將\(a\)平方之後，每個節點會指向它原來指向的節點原來指向的節點。考慮平方之後每個環會變成什麼樣子：很顯然，若此環大小為奇，則仍然是一個奇環；若此環大小為偶，則會分裂成\(2\)個大小為原來一半的環。
現在我們得到\(a\)的圖，需要根據上述變形規律還原出它的平方根。考慮每個環，分\(2\)種情況：
- 大小為奇。它在\(a\)的平方根的圖中可能本來就是一個奇環，也可能是由一個偶環分裂出來的一半；
- 大小為偶。它在\(a\)的平方根的圖中不可能是一個奇環，則只能是一個大小是\(4\)的倍數的偶環分裂出來的一半。
顯然，需要合併的情況都是\(2\)個大小相同的環合併，所以不同大小的環是互相獨立的，我們可以對於每個大小分別考慮還原。分\(2\)種情況：
- 大小為奇。那麼大小為它的每個環要麼是自己還原，要麼是另找一個環合併。顯然自己還原是無條件的，所以我們貪心地選擇將每個環自己還原（將每個節點指向的節點設為平方根圖中該節點指向的節點指向的節點）；
- 大小為偶。此時大小為它的每個環只能是另找一個環合併。於是如果大小為它的環的個數為奇的話，則不能兩兩配對，直接輸出\(-1\)走人；否則任意組合兩兩合併（合併時在\(2\)個環中都任找一個起點，然後\((1,1)\to(2,1)\to(1,2)\to(2,2)\to(1,3)\to\cdots\)（其中\((x,y)\)表示第\(x\)個環中從起點開始數的第\(y\)個節點）作為平方根中的環）。
每個節點都被訪問常數次，所以時間複雜度為\(\mathrm O(n)\)。
下麵貼代碼：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
void read(int &x){//快讀
x=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
void prt(int x){//快寫
if(x>9)prt(x/10);
putchar(x%10^48);
}
const int N=1000000;
int n;
int a[N+1];//平方之後的排列
bool vis[N+1];//DFS時的標記數組
vector<int> v;//此SCC（環）中的點
void dfs(int x){//DFS
if(vis[x])return;
vis[x]=true;
v.pb(x);
dfs(a[x]);
}
vector<vector<int> > vv;//所有環
vector<int> havsz[N+1];//大小為[i]的所有環的編號
int ans[N+1];//a的平方根
int main(){
read(n);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<=n;i++)if(!vis[i]){//找出每個環
v.clear();
dfs(i);
if(v.size()&1){//如果是奇環直接自己還原
vector<int> v0(v.size());//還原之後的環
for(int j=0,now=0;j<v.size();j++,(now+=2)%=v.size())v0[now]=v[j];
for(int j=0;j<v.size();j++)ans[v0[j]]=v0[(j+1)%v.size()];//將還原之後的環用排列的形式存到a的平方根里
}
else vv.pb(v);//否則存下來等到後面找其他環合併
}
for(int i=0;i<vv.size();i++)havsz[vv[i].size()].pb(i);
for(int i=2;i<=n;i+=2)//枚舉偶數大小
if(havsz[i].size()&1)return puts("-1"),0;//不能兩兩配對
else for(int j=0;j<havsz[i].size();j+=2){//枚舉環對
vector<int> &v0=vv[havsz[i][j]]/*第1個環*/,&v1=vv[havsz[i][j+1]]/*第2個環*/,v2(2*v0.size())/*還原之後的環*/;
for(int k=0,now=0;k<v0.size();k++,now+=2)v2[now]=v0[k],v2[now+1]=v1[k];
for(int k=0;k<v2.size();k++)ans[v2[k]]=v2[(k+1)%v2.size()];//將還原之後的環用排列的形式存到a的平方根里
}
for(int i=1;i<=n;i++)prt(ans[i]),putchar(' ');//輸出答案
return 0;
}
