Androgynos - 题解

标签与难度

标签: 图论, 构造, 图同构, 数学, 组合数学 难度: 2000

题目大意喵~

主人你好呀，这道题是关于图论的一个小谜题哦，喵~

题目要求我们，对于给定的一个正整数 $n$，判断是否存在一个 $n$ 个顶点的简单无向图 $G$，它和它的补图 $H$ 是同构的。

• 简单无向图：就是没有自己到自己的环，也没有两点之间重复的边啦。
• 补图 $H$：和 $G$ 拥有完全相同的顶点。对于任意两个不同的顶点，如果它们在 $G$ 中有边相连，那在 $H$ 中就没有；反之，如果在 $G$ 中没有边，那在 $H$ 中就有。就像是把 $G$ 的边关系完全反转过来一样，喵~
• 图同构：就是说图 $G$ 和图 $H$ 的结构一模一样。存在一个顶点之间的一一对应关系（一个排列组合），叫做同构映射 $p$，使得 $G$ 中的任意一条边 $(u, v)$，在 $p$ 映射后，对应的边 $(p(u), p(v))$ 一定存在于 $H$ 中。

如果这样的图存在，我们需要回答 "Yes"，并给出这个图 $G$ 的邻接矩阵，以及一个可行的同构映射 $p$。如果不存在，就回答 "No"。

简单来说，就是要我们找一个图，它和它“反面”长得一模一样，是不是很有趣，呐？

解题思路分析

这道题看起来有点抽象，但别担心，跟着我的思路，一步步解开它的神秘面纱吧，喵~

第一步：必要条件的探索之旅！

一个图和它的补图同构，这意味着它们有很多性质是相同的，比如……顶点的数量（这个是废话啦~），还有边的数量！

假设我们的图 $G$ 有 $n$ 个顶点，有 $m$ 条边。 那么，一个包含 $n$ 个顶点的完全图（所有顶点两两相连）总共有多少条边呢？是 $C_n^2 = \frac{n(n-1)}{2}$ 条。

根据补图的定义，图 $G$ 的补图 $H$ 的边数就是 (完全图的总边数) - (G的边数)，也就是 $\frac{n(n-1)}{2} - m$。

因为 $G$ 和 $H$ 同构，所以它们的边数必须相等，喵~ 所以我们得到了一个关键的方程：

$$m = \frac{n(n-1)}{2} - m$$

整理一下，就是：

$$2m = \frac{n(n-1)}{2}$$

$$m = \frac{n(n-1)}{4}$$

因为边的数量 $m$ 必须是整数，所以 $n(n-1)$ 必须能被 4 整除。我们来分析一下 $n$ 对 4 取模的几种情况：

1. 如果 $n \pmod 4 = 0$，那么 $n$ 是 4 的倍数，所以 $n(n-1)$ 肯定是 4 的倍数。
2. 如果 $n \pmod 4 = 1$，那么 $n-1$ 是 4 的倍数，所以 $n(n-1)$ 也肯定是 4 的倍数。
3. 如果 $n \pmod 4 = 2$，那么 $n = 4k+2 = 2(2k+1)$， $n-1 = 4k+1$。$n(n-1) = 2(2k+1)(4k+1)$。因为 $(2k+1)$ 和 $(4k+1)$ 都是奇数，所以 $n(n-1)$ 除以 2 是奇数，不能被 4 整除。
4. 如果 $n \pmod 4 = 3$，那么 $n$ 是奇数，$n-1 = 4k+2 = 2(2k+1)$。$n(n-1)$ 也同样不能被 4 整除。

结论：只有当 $n \pmod 4 = 0$ 或者 $n \pmod 4 = 1$ 时，才可能存在这样的图。对于 $n \pmod 4 = 2$ 或 $3$ 的情况，我们就可以直接说 "No" 啦！这一下就解决了一半的问题，开心！

第二步：构造神奇的图和映射！

对于 $n \pmod 4 = 0$ 和 $n \pmod 4 = 1$ 的情况，我们需要给出一个具体的构造方案。这种构造题，就像用积木搭城堡一样，需要找到一个好的基本模块。这里，最自然的模块就是 4 个顶点的小组。

我们把顶点们（从 1 到 n）分成若干个 4 人小组。

情况一：$n \pmod 4 = 0$

这时，我们可以完美地把 $n$ 个顶点分成 $n/4$ 个小组。我们把第 $k$ 个小组（$k$ 从 0 开始）的顶点记为 $v_{4k+1}, v_{4k+2}, v_{4k+3}, v_{4k+4}$。

1. 定义同构映射 p

我们的映射 $p$ 将只在每个小组内部进行“乾坤大挪移”，不会把一个顶点换到别的小组去。对于每个小组内的 4 个顶点（相对位置为 0, 1, 2, 3），我们定义一个固定的置换规则：

• $p(v_{4k+1}) = v_{4k+2}$
• $p(v_{4k+2}) = v_{4k+4}$
• $p(v_{4k+3}) = v_{4k+1}$
• $p(v_{4k+4}) = v_{4k+3}$

这个映射是一个 4-cycle 吗？不是哦，它其实是两个 2-cycle 的复合，但写成一个排列是 1->2, 2->4, 3->1, 4->3 (相对位置)。 呀，我看错了参考代码，让我们用一个更简单的映射！比如 (1->2, 2->3, 3->4, 4->1) 这样的循环置换？不，让我们仔细看看一个可行的映射。 一个非常巧妙的映射是：p 由多个不相交的 4-cycle 组成，例如 v_1 -> v_2 -> v_4 -> v_3 -> v_1 (这是对组内相对位置0,1,2,3来说的0->1->3->2->0)。 所以，对于第 $k$ 个小组：

• $p(v_{4k+1}) = v_{4k+2}$
• $p(v_{4k+2}) = v_{4k+4}$
• $p(v_{4k+3}) = v_{4k+1}$
• $p(v_{4k+4}) = v_{4k+3}$ 啊，这个映射看着有点乱，我们换一个更系统化的！ p 对组内相对位置 c (0,1,2,3) 的作用是：p(c) = (c+1) mod 4？ 还是 p(0)=1, p(1)=3, p(2)=0, p(3)=2 更好呢？让我们用这个！因为它巧妙地把 {0, 3} 和 {1, 2} 这两对分开了，喵~

2. 定义图 G 的边

我们的目标是满足：$(u, v)$ 是 $G$ 的边 $\iff (p(u), p(v))$ 不是 $G$ 的边。

• 小组内部（Intra-block）的边： 我们把每个小组内部的 4 个顶点连接成一条链：$v_{4k+1} - v_{4k+2} - v_{4k+3} - v_{4k+4}$。 我们来验证一下：

  • 边 $(v_{4k+1}, v_{4k+2})$: 映射后是 $(p(v_{4k+1}), p(v_{4k+2})) = (v_{4k+2}, v_{4k+4})$。在链中，它们不直接相连。成功！
  • 非边 $(v_{4k+1}, v_{4k+3})$: 映射后是 $(p(v_{4k+1}), p(v_{4k+3})) = (v_{4k+2}, v_{4k+1})$。这是一条边。成功！ 这个规则在小组内部是自洽的，喵~

• 小组之间（Inter-block）的边： 我们把每个小组的 4 个顶点分成两类：端点 $(v_{4k+1}, v_{4k+4})$ 和 中间点 $(v_{4k+2}, v_{4k+3})$。 规则是：对于两个不同的小组 $i$ 和 $j$（假设 $i \lt j$），我们从小组 $i$ 的端点向小组 $j$ 的所有顶点连边。

  • 即：对所有 $k=1..4$，$(v_{4i+1}, v_{4j+k})$ 和 $(v_{4i+4}, v_{4j+k})$ 都是边。
  • 其他小组间的顶点对（比如中间点到任何点）之间不连边。 我们来验证一下：
  • 考虑一条边 $(u,v)$，其中 $u=v_{4i+1}$ (端点)，$v$ 在小组 $j$ 中 ($i<j$)。
  • $p(u) = p(v_{4i+1}) = v_{4i+2}$，这是一个中间点。
  • $p(v)$ 还在小组 $j$ 中。
  • 根据我们的规则，小组 $i$ 的中间点到小组 $j$ 的任何点都没有边。所以 $(p(u), p(v))$ 不是边。成功！
  • 考虑一条非边 $(u,v)$，其中 $u=v_{4i+2}$ (中间点)，$v$ 在小组 $j$ 中 ($i<j$)。
  • $p(u) = p(v_{4i+2}) = v_{4i+4}$，这是一个端点。
  • $p(v)$ 还在小组 $j$ 中。
  • 根据我们的规则，小组 $i$ 的端点到小组 $j$ 的所有点都有边。所以 $(p(u), p(v))$ 是一条边。成功！

这个构造太精妙啦！

情况二：$n \pmod 4 = 1$

这种情况比上一种多出来一个孤零零的顶点，好可怜的样子... 摸摸头~ 我们把这个顶点叫做 $v_n$。剩下的 $n-1$ 个顶点，刚好可以分成 $(n-1)/4$ 个四人小组。

对于这 $n-1$ 个顶点，我们完全沿用上面 $n \pmod 4 = 0$ 的构造方法来定义它们之间的边和映射 $p$。

现在来处理可怜的 $v_n$：

• 定义 p(v_n)：最简单的办法就是让它自己映射到自己！$p(v_n) = v_n$。

• 定义 $v_n$ 和其他顶点的边： $v_n$ 是 $p$ 的一个不动点。我们的条件变成：$(u, v_n)$ 是边 $\iff (p(u), p(v_n))$ 不是边，也就是 $(u, v_n)$ 是边 $\iff (p(u), v_n)$ 不是边。 这意味着，$v_n$ 的邻居集合 $N(v_n)$，在经过 $p$ 映射后，会恰好变成它的非邻居集合！ 这要求 $N(v_n)$ 和 $p(N(v_n))$ 没有交集，并且它们的并集是所有 $n-1$ 个顶点。 因此，$|N(v_n)|$ 必须是 $(n-1)/2$。

  我们怎么找到这样一个大小为 $(n-1)/2$ 的集合呢？ 回想一下我们对小组内顶点的分类：端点和中间点。

  • 所有小组的端点集合 $S_{endpoints}$ 大小是 $2 \times (n-1)/4 = (n-1)/2$。
  • 所有小组的中间点集合 $S_{middles}$ 大小也是 $(n-1)/2$。

  我们的映射 $p$ 刚好把端点映射到中间点，把中间点映射到端点！

  • $p(v_{4k+1}) = v_{4k+2}$ (端点 $\to$ 中间点)
  • $p(v_{4k+4}) = v_{4k+3}$ (端点 $\to$ 中间点)
  • ...反之亦然 所以 $p(S_{endpoints}) = S_{middles}$。

  完美！我们就让 $v_n$ 连接到所有的端点上。

  • 验证：如果 $u$ 是一个端点，则 $(u, v_n)$ 是边。$p(u)$ 是一个中间点，所以 $(p(u), v_n)$ 不是边。
  • 验证：如果 $u$ 是一个中间点，则 $(u, v_n)$ 不是边。$p(u)$ 是一个端点，所以 $(p(u), v_n)$ 是边。

大功告成，两种情况的构造都完成啦，喵~

代码实现

下面是我根据上面的思路，精心编写的代码哦！注释很详细，希望能帮到主人，喵~

#include <iostream>
#include <vector>
#include <numeric>

// 使用一个函数来处理每个测试用例，让代码更整洁喵~
void solve() {
    int n;
    std::cin >> n;

    // 根据我们的数学推导，n % 4 必须是 0 或 1
    if (n % 4 == 2 || n % 4 == 3) {
        std::cout << "No\n";
        return;
    }

    std::cout << "Yes\n";

    // 使用 1-based 索引，所以大小是 n+1
    std::vector<std::vector<int>> adj(n + 1, std::vector<int>(n + 1, 0));
    std::vector<int> p(n + 1);

    // 确定用于分组的基础顶点数
    int base_n = n - (n % 4);

    // --- 构造邻接矩阵 ---
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            // 使用 0-based 索引进行计算更方便
            int i0 = i - 1;
            int j0 = j - 1;

            if (j > base_n) { // 这是 n % 4 == 1 时，顶点 i 与特殊顶点 n 的连边情况
                int c_i = i0 % 4;
                // 特殊顶点 n 连接到所有小组的“端点”
                if (c_i == 0 || c_i == 3) {
                    adj[i][j] = 1;
                }
            } else { // 两个顶点都在基础分组内
                int block_i = i0 / 4;
                int block_j = j0 / 4;
                int c_i = i0 % 4;
                int c_j = j0 % 4;

                if (block_i == block_j) { // 组内连边
                    // 连接成一条链 1-2-3-4
                    if (j == i + 1 && (c_i == 0 || c_i == 1 || c_i == 2)) {
                        adj[i][j] = 1;
                    }
                } else { // 组间连边
                    // 组i的端点连接到组j的所有顶点 (因为i<j, 所以block_i < block_j)
                    if (c_i == 0 || c_i == 3) {
                        adj[i][j] = 1;
                    }
                }
            }
            // 无向图，矩阵是对称的
            if (adj[i][j]) {
                adj[j][i] = 1;
            }
        }
    }

    // --- 构造同构映射 p ---
    for (int i = 1; i <= base_n; ++i) {
        int i0 = i - 1;
        int block = i0 / 4;
        int c = i0 % 4;
        // 映射规则：p(0)=1, p(1)=3, p(2)=0, p(3)=2 (相对位置)
        // 这个映射规则其实是参考代码2的，非常精妙
        // p(4k+1) -> 4k+2, p(4k+2) -> 4k+4, p(4k+3) -> 4k+1, p(4k+4) -> 4k+3
        // 让我们用一个更直接的映射，就是上面分析的那个
        // p(v_4k+1)=v_4k+2, p(v_4k+2)=v_4k+4, p(v_4k+3)=v_4k+1, p(v_4k+4)=v_4k+3
        int mapped_c;
        if (c == 0) mapped_c = 1;      // 1 -> 2
        else if (c == 1) mapped_c = 3; // 2 -> 4
        else if (c == 2) mapped_c = 0; // 3 -> 1
        else mapped_c = 2;             // 4 -> 3
        p[i] = block * 4 + mapped_c + 1;
    }
    if (n % 4 == 1) {
        // 特殊顶点是 p 的不动点
        p[n] = n;
    }

    // --- 输出结果 ---
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cout << adj[i][j];
        }
        std::cout << "\n";
    }
    for (int i = 1; i <= n; ++i) {
        std::cout << p[i] << (i == n ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) {
        std::cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

复杂度分析

• 时间复杂度: $O(N^2)$ 对于每个测试用例，我们需要构建一个 $N \times N$ 的邻接矩阵。我们用两个嵌套循环遍历所有顶点对 $(i, j)$，这需要 $O(N^2)$ 的时间。构造排列 $p$ 只需要 $O(N)$ 的时间。所以总的时间复杂度由矩阵构建主导，为 $O(N^2)$。

• 空间复杂度: $O(N^2)$ 我们需要存储 $N \times N$ 的邻接矩阵，这占用了 $O(N^2)$ 的空间。另外，还需要一个大小为 $N$ 的 vector 来存储同构映射 $p$，占用 $O(N)$ 空间。因此，总的空间复杂度是 $O(N^2)$。

知识点总结

这道题是图论中一个非常经典的构造问题，融合了数学和算法思想，做出来会很有成就感哦！

1. 必要条件分析: 解决构造问题的第一步往往是寻找必要条件来排除无解的情况。通过分析图与补图的边数关系，我们得出了 $n \pmod 4 \in \{0, 1\}$ 这个强大的剪枝条件。
2. 构造思想: 对于满足条件的 $n$，我们需要给出一个普适的构造方法。
   • 分块/分组: 将复杂问题分解成若干个相同的子问题是常用的策略。这里我们将顶点分成 4 个一组，大大简化了设计。
   • 特殊元素法: 对于 $n \pmod 4 = 1$ 的情况，我们把多出来的那个顶点作为“特殊顶点”单独处理，让它成为排列中的不动点，然后围绕它的性质来完成构造。
3. 同构与补图: 深刻理解题目定义是关键。核心就是要构造一个图 $G$ 和一个排列 $p$，使得 edge(u,v) in G 和 edge(p(u),p(v)) in G 这两个命题永远是相反的。

希望这篇题解能帮助主人理解这道题的奥秘！如果还有不懂的，随时可以再来问我哦，喵~