Beautiful Graph - 题解

比赛与标签

比赛: Educational Codeforces Round 56 (Rated for Div. 2) 标签: dfs and similar, graphs 难度: *1700

题目大意喵~

主人，你好喵~！今天我们来解决一道非常有趣的图论问题，叫做 "Beautiful Graph" 呐！

题目是这样子的：我们有一个无向无权图，包含 n 个顶点和 m 条边。我们的任务是给每个顶点分配一个数字，可以是 1、2 或 3。

什么样的图才算 "beautiful"（漂亮）呢？规则是：对于图中的任意一条边，连接的两个顶点上的数字之和必须是奇数。

我们需要计算出，有多少种不同的分配数字的方法，能让整个图变得 "beautiful"。因为答案可能会很大，所以要对 998244353 取模哦。

输入格式：会先给一个整数 t，表示有 t 组测试数据。对于每组数据，会给出顶点的数量 n 和边的数量 m，接着是 m 行，每行表示一条连接两个顶点的边。

输出格式：对于每组测试数据，输出一个整数，代表漂亮的分配方案总数。

解题思路大揭秘！

喵哈哈，这道题看起来有点复杂，但只要我们抓住关键点，它就会变得像毛线球一样好玩啦！

问题的核心在于“和为奇数”这个条件。主人想想看，两个整数相加，什么时候和是奇数呀？没错喵！就是一个奇数加上一个偶数的时候！

我们能用的数字是 {1, 2, 3}。

奇数有：{1, 3} （两种选择）
偶数有：{2} （一种选择）

这意味着，对于任何一条边连接的两个顶点，一个顶点上必须放奇数，另一个顶点上必须放偶数。它们俩的“奇偶性”必须不同！

这听起来是不是很熟悉？这不就是 二分图 的定义嘛！一个图是二分图，当且仅当它的所有顶点可以被分成两个互不相交的集合 A 和 B，使得所有边都连接着一个 A 集合中的点和一个 B 集合中的点。

所以，我们的问题就转化为了：

判断给定的图是不是一个二分图。
如果是，计算有多少种合法的染色方案。

如何判断二分图呢？ 我们可以用 BFS（广度优先搜索） 或者 DFS（深度优先搜索） 来进行染色。这里我们用 BFS 举例，喵~

我们用一个 color 数组来记录每个顶点的颜色（比如 0 和 1），初始化为 -1（表示未染色）。
遍历所有顶点。如果一个顶点 i 还没被染色，说明我们发现了一个新的连通块，就从它开始进行 BFS。
把顶点 i 染成颜色 0，然后放进队列。
当队列不为空时，取出一个顶点 u，遍历它的所有邻居 v：
- 如果 v 还没被染色，就把它染成和 u 相反的颜色（1 - color[u]），然后把它也加入队列。
- 如果 v 已经被染色了，并且颜色和 u 相同，那就说明出现了冲突！这意味着图里存在一个奇数长度的环，它不是二分图。这种情况下，不可能满足条件，方案数就是 0。

如何计算方案数呢？ 如果整个图（或者某个连通块）被成功地染成了二分图，我们就可以来计算方案数了。

假设在一个连通块中，我们染出了 cnt0 个颜色为 0 的顶点和 cnt1 个颜色为 1 的顶点。现在我们有两种大的分配策略：

策略一：把颜色 0 的顶点分配为奇数，颜色 1 的顶点分配为偶数。
- cnt0 个颜色 0 的顶点，每个都有 2 种选择（1 或 3），所以有 2^cnt0 种方法。
- cnt1 个颜色 1 的顶点，每个只有 1 种选择（2），所以有 1^cnt1 = 1 种方法。
- 此策略下的总方法数是 2^cnt0。
策略二：把颜色 0 的顶点分配为偶数，颜色 1 的顶点分配为奇数。
- cnt0 个颜色 0 的顶点，每个只有 1 种选择（2），所以有 1^cnt0 = 1 种方法。
- cnt1 个颜色 1 的顶点，每个都有 2 种选择（1 或 3），所以有 2^cnt1 种方法。
- 此策略下的总方法数是 2^cnt1。

根据加法原理，这个连通块的总方案数就是 (2^cnt0 + 2^cnt1) 种。

处理多个连通块 如果图不是连通的，它会由好几个独立的连通块组成。每个连通块的染色方案都是独立的。根据乘法原理，我们只需要把每个连通块的方案数乘起来，就是最终的答案啦！

总结一下完整流程：

预处理计算 2 的幂次，方便之后使用。
初始化总答案 ans = 1。
遍历所有顶点 i 从 1 到 n。
如果顶点 i 还没被染色，就从它开始进行一次 BFS：
- 在 BFS 过程中进行二分图染色，并统计两种颜色的顶点数 cnt0 和 cnt1。
- 如果在染色过程中发现冲突（邻居颜色相同），说明图不是二分图，直接把 ans 设为 0，并结束所有循环。
- 如果这个连通块是二分图，计算它的方案数 ways = (2^cnt0 + 2^cnt1) % mod。
- 将这个方案数乘到总答案中：ans = (ans * ways) % mod。
最后输出 ans 就好啦！

代码实现喵！

下面就是具体的代码实现了，我已经加上了详细的注释，希望能帮到主人哦~

cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 定义常量，最大顶点数和模数
const int MAX_N = 300000;
const long long mod = 998244353;

int main() {
    // 预处理2的幂次，因为我们会频繁用到，喵~
    vector<long long> power2(MAX_N + 1);
    power2[0] = 1;
    for (int i = 1; i <= MAX_N; i++) {
        power2[i] = (power2[i - 1] * 2) % mod;
    }

    // 优化输入输出速度
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        // 使用邻接表来存图
        vector<vector<int>> graph(n + 1);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        // color数组：-1表示未染色，0和1表示两种颜色
        vector<int> color(n + 1, -1);
        long long ans = 1;
        bool global_ok = true; // 标记整个图是否是二分图

        // 遍历所有顶点，确保处理所有连通块
        for (int i = 1; i <= n && global_ok; i++) {
            if (color[i] != -1) continue; // 如果已经染过色，就跳过

            // 开始对新的连通块进行BFS
            queue<int> q;
            q.push(i);
            color[i] = 0; // 给起始点染上颜色0
            int cnt0 = 0, cnt1 = 0; // 统计两种颜色的顶点数
            bool conflict = false; // 标记当前连通块是否有冲突

            while (!q.empty() && !conflict) {
                int u = q.front();
                q.pop();

                // 统计当前顶点颜色
                if (color[u] == 0) cnt0++;
                else cnt1++;

                // 遍历邻居
                for (int v : graph[u]) {
                    if (color[v] == -1) { // 如果邻居未染色
                        color[v] = color[u] ^ 1; // 染上相反的颜色
                        q.push(v);
                    } else if (color[v] == color[u]) { // 如果邻居颜色和自己相同
                        conflict = true; // 发现冲突！不是二分图
                        break;
                    }
                }
            }

            if (conflict) {
                global_ok = false; // 只要有一个连通块不是二分图，总方案就是0
            } else {
                // 计算这个连通块的方案数 = (2^cnt0 + 2^cnt1)
                long long ways_component = (power2[cnt0] + power2[cnt1]) % mod;
                // 用乘法原理累积总方案数
                ans = (ans * ways_component) % mod;
            }
        }

        if (!global_ok) {
            cout << 0 << '\n';
        } else {
            cout << ans << '\n';
        }
    }

    return 0;
}

复杂度分析的说~

时间复杂度: O(N + M) 的说。这里的 N 和 M 是单个测试用例中的顶点数和边数。因为我们对每个顶点和每条边最多访问常数次（在BFS中），所以整体的时间复杂度是线性的。对于所有测试用例，总和也是线性的，符合题目要求。
空间复杂度: O(N + M) 的说。我们主要用了邻接表来存储图，它的大小是 O(N + M)，还有一个 color 数组大小是 O(N)。所以总的空间复杂度也是 O(N + M) 喵~

知识点与总结

这道题真是太棒了，把图论和计数巧妙地结合在了一起呢！

核心思想：模型转换 问题的关键在于把“和为奇数”这个算术条件，转化为图论中的“二分图”模型。这是解题的第一步，也是最重要的一步喵！能够发现这个转化，问题就解决了一大半。
核心算法：二分图判定 我们可以用 BFS 或 DFS 来高效地判断一个图是否是二分图，并在这个过程中顺便把两个顶点集合的大小统计出来。这是图论中的一个基础且重要的算法。
计数原理：加法与乘法原理
- 加法原理：对于一个连通块，我们将奇数分配给集合A、偶数分配给集合B，或者反过来。这是两种互斥的方案，所以总方案数是两者相加。
- 乘法原理：图中的不同连通块是相互独立的，一个块的染色方式不影响另一个。所以总方案数是所有连通块方案数的乘积。
编程技巧
- 预处理幂次：因为要多次计算 2 的幂，提前用一个数组算好存起来，可以避免重复计算，大大加快速度的说。
- 处理非连通图：一定要用一个外层循环遍历所有顶点，确保每个连通块都被访问到。不要想当然地认为图是连通的哦！

希望这篇题解能帮助主人更好地理解二分图和计数问题！继续加油，你超棒的喵~！

Beautiful Graph - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵！ ​

复杂度分析的说~ ​

知识点与总结 ​