洛谷題目頁面傳送門 & 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]\cap\mathbb Z,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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/89845.html
標籤：C++
上一篇：多重背包問題