[BZOJ4466][Jsoi2013]超立方体

试题描述

超立方体是立方体在高维空间内的拓展（其在 \(2\) 维情况下退化为正方形，\(1\) 维情况下退化成线段）。在理论计算机科学领域里，超立方体往往可以和 \(2\) 进制编码联系到一起。对理论计算机科学颇有研究的 Will 自然也会对超立方体有着自己的思考。

QAQ

上图就是在 \(0 \sim 4\) 维空间内超立方体所对应的图形。显然我们可以把超立方体的每个顶点看成一个点，每一条棱看成一条边，这样就会得到一个无向图，我们称之为超立方图。

\(D\) 维空间内的超立方图有 \(2^D\) 个点，我们把这些点从 \(0\) 到 \(2^D - 1\) 依次编号。

有一个有趣而重要的充要结论是：一定存在一种编号的方式，使得图中任意两个有边相连的顶点的编号的 2进制码中，恰好有一位不同。

在 \(2\) 维和 \(3\) 维空间内这个结论可以这样形象的理解：

对于 \(2\) 维空间，我们只要把这个正方形放到第一象限内，使得 \(4\) 个顶点的坐标按逆时针顺序依次为 \((0,0)\)，\((1,0)\)，\((1,1)\)，\((0,1)\)，然后再把坐标看成 \(2\) 位 \(2\) 进制数，依次将这 \(4\) 个点编号为 \(0\)，\(1\)，\(3\)，\(2\) 即可。

对于 \(3\) 维空间，同样我们可以将立方体的一个顶点与原点重合，并使得所有棱均平行于坐标轴，然后分别确定这 \(8\) 个点的坐标，最后把 \(3\) 维空间内的坐标看成一个 \(3\) 位 \(2\) 进制数即可。对于 \(D\) 维空间，以此类推。

现在对于一个 \(N\) 个点 \(M\) 条边的无向图（每个点从 \(0\) 到 \(N-1\) 编号），Will 希望知道这个图是否同构于一个超立方图。

输入

第一行包含一个整数 \(Q\) 表示此数据中一共包含 \(Q\) 个询问。

接下来 \(Q\) 组询问，每一组询问的输入格式如下：

第一行包含两个整数 \(N\) 和 \(M\)，接下来 \(M\) 行，每行 \(2\) 个不同的整数 \(x\)，\(y\)，表示图中存在一条无向边连接编号为 \(x\) 和 \(y\) 的点（\(0 \le x,y < N\)）

输出

对于每一个询问分别输出一行，内容如下：

1、如果询问中给定的图不同构于任何一个超立方图，输出 \(-1\)；

2、如果同构于某一个超立方图，那么请给图中这 \(N\) 个点重新编号，并在这一行输出 \(N\) 个用空格隔开的整数，表示原图中每个点新的编号，使得重新编号后，满足题目中所述的结论。

注意：输出文件的每一行，要么仅包含一个整数 \(-1\)，要么则应包含一个由 \(0\) 到 \(N-1\) 这 \(N\) 个数组成的排列。如果有多组解输出任意一个均可。

输入示例

输出示例

-1
-1
0 6 1 5 4 2 3 7

数据规模及约定

\(Q \le 3,N \le 32768,M \le 1000000\)

题解

这题看上去有点吓人，但其实就是一个模拟，当然需要分析一些性质。

首先 \(N\) 必须是 \(2\) 整数次幂；\(M\) 也要满足一定条件，你可以一维一维地递推出 \(d\) 维下的超立方体有多少条棱，令 \(e_d\) 表示那个答案，则 \(e_0 = 0, e_i = 2e_{i-1} + 2^{i-1}\)，判一下 \(M\) 是否等于 \(e_{\log N}\) 即可。（那个递推式的意思就是，\(d\) 维是由 \(d-1\) 的超立方体平移得到的，这样原来的棱数会倍增，同时每个点的平移轨迹会产生一条新棱，所以要加上 \(d-1\) 维时的点数）

然后随便规定一个点的标号为 \(0\)，将其周围的点的编号依次设为 \(2^0, 2^1, 2^2, \cdots , 2^d\)，然后开始 bfs，当搜到一个未确定标号的点时，若图合法则一定会后两个邻居标号已经确定（因为合法的图一定会有许多的四元环），那么就可以用这两个标号计算出它的标号。最后再检查一下是否符合题意。

中间有许多细节，实现时要注意。

然后还有一个问题就是为什么可以随便选一个点开始确定，这是因为立方体高度对称，它可以任意旋转；在 \(d\) 维的超立方体中，每个点出去一定都会有刚好 \(d\) 条互相垂直的棱，所以谁都能作为“坐标原点”，它连出去的边就是坐标轴了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 32790
#define maxm 2000010

int n, m, head[maxn], nxt[maxm], to[maxm], D;

bool check_num(int n, int m) {
	int d = 0;
	while(!(n & 1)) n >>= 1, d++; D = d;
	if(n > 1) return 0;
	int e = 0, node = 1;
	rep(i, 1, d) e = (e << 1) + node, node <<= 1;
	if(m != e) return 0;
	return 1;
}

void AddEdge(int a, int b) {
	to[m] = b; nxt[m] = head[a]; head[a] = m++;
	swap(a, b);
	to[m] = b; nxt[m] = head[a]; head[a] = m++;
	return ;
}

int Q[maxn], hd, tl, tag[maxn];
bool vis[maxn], used[maxn];
int confirm(int u) {
	int v1 = -1, v2 = -1;
	for(int e = head[u]; e != -1; e = nxt[e]) if(vis[to[e]]) {
		if(v1 < 0) v1 = to[e];
		else{ v2 = to[e]; break; }
	}
	if(v2 < 0) return -1;
	int Xor = tag[v1] ^ tag[v2], cdiff = 0;
	rep(i, 0, D - 1) if(Xor >> i & 1) cdiff++;
	if(cdiff != 2) return -1;
	tag[u] = 0;
	rep(i, 0, D - 1) if(!(Xor >> i & 1)) tag[u] |= tag[v1] & (1 << i);
	if(!used[tag[u]]) return used[tag[u]] = 1, 0;
	// attempt 1
	tag[u] ^= Xor;
	if(!used[tag[u]]) return used[tag[u]] = 1, 0;
	tag[u] ^= Xor;
	// attempt 2
	int oXor = Xor;
	rep(i, 0, D - 1) if(Xor >> i & 1){ Xor ^= 1 << i; break; }
	tag[u] ^= Xor;
	if(!used[tag[u]]) return used[tag[u]] = 1, 0;
	tag[u] ^= Xor;
	// attempt 3
	Xor = oXor;
	dwn(i, D - 1, 0) if(Xor >> i & 1){ Xor ^= 1 << i; break; }
	tag[u] ^= Xor;
	if(!used[tag[u]]) return used[tag[u]] = 1, 0;
	// attempt 4
	return -1;
}
bool check() {
	rep(u, 0, n - 1) {
		for(int e = head[u]; e != -1; e = nxt[e]) {
			int Xor = tag[u] ^ tag[to[e]], cdiff = 0;
			rep(i, 0, D - 1) if(Xor >> i & 1) cdiff++;
			if(cdiff != 1) return 0;
		}
	}
	return 1;
}
void bfs() {
	hd = tl = 0; Q[++tl] = 0;
	tag[0] = 0; vis[0] = used[0] = 1;
	int c = 0;
	for(int e = head[0]; e != -1; e = nxt[e]) {
		if(!vis[to[e]]) vis[to[e]] = used[1<<c] = 1, Q[++tl] = to[e], tag[to[e]] = 1 << c;
		c++; if(c > D) return (void) puts("-1");
	}
	if(c != D) return (void)puts("-1");
	hd++;
	while(hd < tl) {
		int u = Q[++hd];
		c = 0;
		for(int e = head[u]; e != -1; e = nxt[e]) {
			if(!vis[to[e]]) {
				vis[to[e]] = 1; Q[++tl] = to[e];
				if(confirm(to[e]) == -1) return (void)puts("-1");
			}
			c++;
		}
		if(c != D) return (void)puts("-1");
	}
	rep(i, 0, n - 1) if(!vis[i]) return (void)puts("-1");
	if(!check()) return (void)puts("-1");
	rep(i, 0, n - 1) printf("%d%c", tag[i], i < n - 1 ? ' ' : '\n');
	return ;
}

void work() {
	n = read(); int M = read();
	m = 0; memset(head, -1, sizeof(head));
	rep(i, 1, M) {
		int a = read(), b = read();
		AddEdge(a, b);
	}
	if(!check_num(n, M)) return (void)puts("-1");
	
	if(n == 1) return (void)puts("0");
	memset(vis, 0, sizeof(vis));
	memset(used, 0, sizeof(used));
	bfs();
	
	return ;
}

int main() {
	int T = read();
	while(T--) work();
	
	return 0;
}

[BZOJ4466][Jsoi2013]超立方体