题目链接

http://codeforces.com/problemset/problem/765/D

题目大意

给你一个函数 $f(x)$ ，让你求出两个函数 $g(x)$ 和 $h(x)$ 使得 $g(h(x)) = x$ 和 $h(g(x)) = f(x)$ 成立，对于 $f(x)$ 和 $g(x)$ ， $x$ 的定义域为 $1$ 到 $n$ ，对于 $h(x)$ 定义域为 $1$ 到 $m$

你需要求出全部的 $g(x)$ 和 $h(x)$ 以及 $m$ ，无解输出 $-1$

题目分析

可观察得到三个式子

$$g(h(g(x))) = g(x) = g(f(x))$$

$$h(g(h(x))) = f(h(x)) = h(x)$$

$$h(g(h(g(x)))) = f(x) = f(f(x))$$

所以由第三个式子可知必有 $f(x) = f(f(x))$ 时才有解

由第二个式子可知 $h(x)$ 里的元素是 $x = f(x)$ 构成的

$m$ 就是 $x=f(x)$ 的个数

在通过第一个式子确定 $g(x)$ 的值

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

queue <int> q;

int n, m;

int f[100005];
int g[100005];
int h[100005];

int main(){
    int i, j;
    bool flag = true;
    
    cin >> n;
    
    for(i=1;i<=n;i++){       
        cin >> f[i];
        if(i == f[i]){
            q.push(i);
        }
    }
    
    for(i=1;i<=n;i++){
        if(f[i] != f[f[i]]){
            flag = false;
        }
    }
    
    m = 0;
    
    while(!q.empty()){
        m++;
        h[m] = q.front();
        g[h[m]] = m;
        q.pop();
    }
    
    for(i=1;i<=n;i++){
        g[i] = g[f[i]];
    }
    
    if(!flag){
        cout << -1 << endl;
    }else{
        
        cout << m << endl;
        
        for(i=1;i<n;i++){
            cout << g[i] << " ";
        }
        cout << g[n] << endl;
        
        for(i=1;i<m;i++){
            cout << h[i] << " ";
        }
        cout << h[m] << endl;
    }
    
    return 0;
}