CF612E Square Root of Permutation 题解 图论建图题

题目链接: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;
}
上一篇:爬虫应对js混淆的方法


下一篇:网络通信 --> TCP三次握手和四次挥手