题解 P5260 【[JSOI2013]超立方体】

· · 题解

题目大意：给定 n 个节点 m 条边的无向图，判断其是否同构于一超立方图。若同构，请将点重新编号使得相邻两个点的编号在二进制下恰有一位不同。

首先，一个 k 维超立方体有两个性质：

  1. 有 2^k 个顶点

  2. 有 k\cdot2^{k-1} 条边

对于第二条性质，注意到每个顶点会向外连出 k 条边，一共有 2^k 个顶点，然而每条边会被算两次，因此共有 k\cdot2^{k-1} 条边。

因此，通过判断 n,m 是否满足上述两个条件，便可初步排除那些非超立方图：

(n & (n - 1)) || (m != log2(n) * n / 2)

但仅仅这样还不足以判断，例如样例中第二组询问：

虽然 n=m=4 满足性质，但它不是正方形。这时我们可以利用题目提供的性质：如果这个图同构于超立方图，那么可以找到一个编号方式使得相邻两点编号在二进制下恰有一位不同。

事实上，它的逆定理同样成立。因此我们可以先尝试找出一种编号方案，若找不到说明它并非超立方图。

怎么编号呢？假设有一个 k 维的超立方图。

首先得安排一个 0 号吧，处于超立方体的对称性，这个 0 号选哪个点都无所谓（我选的是原来的 0 号节点）。

然后，对于它连向的 k 个节点，分别编号为 1,2,4,\dots,2^{k-1}。这样可以确保在二进制下与 0 仅有一位不同。

接着有意思的部分来了。定义一个节点的深度为其到 0 号节点的距离，则任意一个节点编号中 1 的个数就等于它的深度。而深度为 d 的点，则恰有 d 个深度为 d-1 的节点与之相连（即将编号中 d 个 1 任意修改一个变为 0）。因此将所有与之相连的深度为 d-1 的点的编号或起来，便可得到深度为 d 的点的编号。 按照深度 BFS 一遍即可得到所有点的编号。

以上三步便是如何给超立方图编号的过程。其实个人认为可以这么类比：第一步确定原点，第二步确定坐标轴，第三步分层构建出整个超立方体。

编号完后记得 check 一遍，如果方案非法则说明原图不是超立方图。

#include<bits/stdc++.h>
#define nb 33333
using namespace std;

int q, n, m, a[nb];
vector<int> G[nb];

bool bfs(){
    a[0] = 0;
    // 确定原点
    queue<int> q;
    for(int i = 0; i < G[0].size(); i++){
        q.push(G[0][i]);
        a[G[0][i]] = 1 << i;
        // 确定坐标轴
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            if(a[v] != -1) continue;
            q.push(v);
            a[v] = 0;
            for(int j = 0; j < G[v].size(); j++){
                int w = G[v][j];
                if(a[w] != -1) a[v] |= a[w];
                // 将深度恰好小 1 的点编号或起来就是此点编号
            }
        }
    }
    for(int u = 0; u < n; u++){
        for(int i = 0; i < G[u].size(); i++){
            int tmp = a[G[u][i]] ^ a[u];
            if(tmp & (tmp - 1)) return 1;
            // 验证编号方案是否合法
            // 如果相邻节点编号异或得到不是 2 的幂，说明方案非法
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    for(cin >> q; q; q--){
        cin >> n >> m;
        memset(a, -1, sizeof(a));
        for(int i = 0; i < n; i++) G[i].clear();
        for(int i = 0, u, v; i < m; i++){
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        if((n & (n - 1)) || (m != log2(n) * n / 2) || bfs()){
            // n, m 不符合条件或无合法方案，说明原图不是超立方图
            cout << "-1\n";
            continue;
        }
        for(int i = 0; i < n; i++){
            cout << a[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

// 顺便帮忙填了 SPJ 的坑，如发现有 bug 欢迎指正