一个变换题

给定f(x),[1,n]->[1,n]

构造g(x),h(x)满足：

g(h(x))=x [1,n]->[1,m]

h(g(x))=f(x) [1,m]->[1,n]

根据已知条件，等效替换变形：

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

=>h(x)=f(h(x))

=>h(g(x))=f(h(g(x)))

=>f(x)=f(f(x)) //是不是有点类似并查集找爸爸

另一方面：

g(h(g(x)))=g(x)

=>g(x)=g(f(x))

这里我们又可以发现f,g,h三个函数的值域其实都是[1,m],等价于将n个元素分为m类

那么题目意思是不是可以转化成：

f(i):找i这个元素的爸爸元素是谁

g(i):找元素i属于哪一类

h(i):找第i类的爸爸元素是谁

这不就是很经典的(排名<<=>>权值)互换函数么

int n, m;

int f[N], g[N], h[N];

int vis[N];

int main()

{

#ifndef ONLINE_JUDGE

    file("test");

#endif

    sdf(n);

    For(i, 1, n) sdf(f[i]);

    For(i, 1, n)

    {

        if (f[f[i]] != f[i])

        {

            cout << -1;

            return 0;

        }

        if (!vis[f[i]])

            h[++m] = f[i], g[f[i]] = m,vis[f[i]]=1;

        g[i] = g[f[i]];

    }

    cout << m << endl;

    For(i, 1, n) cout << g[i] << " ";

    cout << endl;

    For(i, 1, m) cout << h[i] << " ";