题目链接:http://codeforces.com/contest/612/problem/E
题目大意:给你一个 \(1\) 到 \(n\) 的排列,求一个 \(1\) 到 \(n\) 的排列 \(q\) 满足 \(q_{q_i} = p_i\)。无解则输出 \(-1\)。
解题思路(完全参照自 SovietPower大佬的博客):
对排列 \(q_i\) 我们建一个图,边为 \(i \rightarrow q_i\)。显然这张图是有几个环构成的。
对于 \(p_i\)(即 \(q_{q_i}\)),原来 \(q_i\) 中的奇环在 \(p_i\) 中也是由同样的数据组成的奇环,只不过排列顺序变成了 \(1,2,5,\ldots,n,2,4,\ldots,n-1\);原来的偶环会变成两个大小相等的偶环(一个由 \(1,3,5,\ldots,n-1\) 构成,一个由 \(2,4,6\ldots,n\) 构成)。
所以对 \(p_i\) 建图,找出对应的环。奇环单独处理,两个大小相同的偶环一起处理。就能还原出 \(q_i\) 对应的图了。
示例代码如下:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n, p[maxn];
int sz[maxn], head[maxn], tmp[maxn], m, q[maxn];
bool vis[maxn];
bool cmp(int i, int j) {
return sz[i] < sz[j];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", p+i);
for (int i = 1; i <= n; i ++) {
if (!vis[i]) {
head[m++] = i;
int j = i;
while (!vis[j]) {
vis[j] = true;
sz[i] ++;
j = p[j];
}
if (j != i) {
puts("-1");
return 0;
}
}
}
sort(head, head+m, cmp);
for (int i = 0; i < m; i ++) {
int u1 = head[i], u2 = head[i+1];
if (sz[u1] % 2) { // 奇环
int x = u1, y = 0;
for (int j = 0; j < sz[u1]; j ++) {
tmp[y] = x;
y = (y + 2) % sz[u1];
x = p[x];
}
assert(x == u1);
for (int j = 0; j < sz[u1]; j ++)
q[ tmp[j] ] = tmp[(j+1) % sz[u1]];
}
else { // 偶环
if (i == m-1 || sz[u1] != sz[u2]) {
puts("-1");
return 0;
}
// 处理偶环
int x = u1, y = u2;
for (int i = 0; i < sz[u1]; i ++) {
q[x] = y;
q[y] = p[x];
x = p[x];
y = p[y];
}
i ++; // 多加上1
}
}
for (int i = 1; i <= n; i ++) printf("%d ", q[i]);
return 0;
}