BZOJ4466 [JSOI2013] 超立方体

2018 年 03 月 14 日发布.

Description

定义“超立方图”为：有$2^k$个点，以$k$位二进制数编号，两个点之间有边当且仅当它们的编号恰有一位不同。给出一个图，问它是否与“超立方图”同构。如果是，输出任意一种点与点的对应方案。($n \leqslant 32768$)

Solution

先判断点数和边数、每个点的度数。

之后假设同构，求出同构方案后再check一遍。

显然超立方图的每个点都是对称的，于是我们任取一个点作为0，与它相邻的$k$个点编号为$2^i, i=0\dots k-1$。

之后，所有与$0$距离为$2$的点一定恰好与两个距离为$1$的点连边，且它的编号为这两个点编号的bit or。

与$0$距离为$3$的点的编号是所有与它相连的已知编号的点（距离一定是$2$）的bit or。

以此类推。bfs一遍即可。

最后不要忘记check。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 33000;
const int M = 2000050;
int pre[N], nxt[M], to[M], cnt, deg[N];
int A[N], que[N];
bool vis[N];
inline void addEdge(int x, int y) {
  ++deg[x];
  nxt[cnt] = pre[x];
  to[pre[x] = cnt++] = y;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m, x, y;
    scanf("%d%d", &n, &m);
    int k = 1;
    while ((1 << k) < n) ++k;
    memset(pre, -1, sizeof pre);
    memset(deg, 0, sizeof deg);
    cnt = 0;
    while (m--) {
      scanf("%d%d", &x, &y);
      addEdge(x, y);
      addEdge(y, x);
    }
    bool ok = true;
    for (int i = 0; i < n; ++i)
      ok = ok && deg[i] == k;
    if (!ok) { puts("-1"); continue; }
    memset(A, 0, sizeof A);
    memset(vis, 0, sizeof vis);
    int hd = 0, tl = 0;
    vis[0] = true;
    for (int i = pre[0], j = 1; ~i; i = nxt[i], j <<= 1)
      A[que[tl++] = to[i]] = j;
    while (hd < tl) {
      int x = que[hd++];
      vis[x] = true;
      for (int i = pre[x]; ~i; i = nxt[i])
        if (!vis[to[i]]) {
          if (!A[to[i]]) que[tl++] = to[i];
          A[to[i]] |= A[x];
        }
    }
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < n; ++i) vis[A[i]] = true;
    for (int i = 0; i < n; ++i) ok = ok && vis[i];
    if (!ok) { puts("-1"); continue; }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < k; ++j) vis[A[i] ^ (1 << j)] = false;
      for (int j = pre[i]; ~j; j = nxt[j]) vis[A[to[j]]] = true;
      for (int j = 0; j < k; ++j) ok = ok && vis[A[i] ^ (1 << j)];
    }
    if (!ok) { puts("-1"); continue; }
    for (int i = 0; i < n; ++i)
      printf("%d ", A[i]);
    puts("");
  }
}