square_root_of_permutation.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 1000100
int N, q[MAXN], p[MAXN], visited[MAXN];
vector<vector<int> > cycle[MAXN];
void input(){
    scanf("%d", &N);
    for(int i =1 ;i <= N; i++)
        scanf("%d", &q[i]);
}
void buildCycle(){
    //순열 순회
    for(int i = 1; i<= N; i++){
        if(visited[i])
            continue;

        //방문한 적 없는 정점 일 때 진입

        //사이클 저장
        vector<int> cur(1, i);
        int where = i;
        visited[where] = true;
        while(q[where] != i){
            where = q[where];
            visited[where] = true;
            cur.push_back(where);
        }
        cycle[cur.size()].push_back(cur);
    }
}
bool isValid(){
    //길이가 짝수인 사이클이 쌍으로 존재하는지 검사
    for(int i = 2; i <= N; i += 2)
        if(cycle[i].size() % 2 == 1)
            return false;

    return true;
}
void squareRootPermutaion(){
    for(int i = 1; i<= N; i++){
        if(i%2){
            //홀수 일 때, 바로 복원 가능
            for(auto c : cycle[i]){
                for(int j = 0; j < i; j++){
                    p[c[j]] = c[(j+i/2+1)%i];
                }
            }
        }else{
            //짝 수 일때, 번갈아가면서 나열하기
            for(int k = 0; k < cycle[i].size(); k += 2){
                auto a = cycle[i][k];
                auto b = cycle[i][k+1];
                for(int j = 0 ; j < i ; j++){
                    p[a[j]] = b[j];
                    p[b[j]] = a[(j+1)%i];
                }
            }
        }
    }
    for(int i = 1; i<= N; i++)
        printf("%d ", p[i]);
}
int main(){
    input();
    buildCycle();
    if(!isValid()){
        printf("-1");
        return 0;
    }
    squareRootPermutaion();
    return 0;
}