无向图染色

题目描述

给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？

输入描述

第一行输入M(图中节点数) N(边数)

后续N行格式为：V1 V2表示一个V1到V2的边。

数据范围：1 <= M <= 15,0 <= N <= M * 3，不能保证所有节点都是连通的。

输出描述

输出一个数字表示染色方案的个数。

示例1

输入：
4 4
1 2
2 4
3 4
1 3

输出：
7

说明：
4个节点，4条边，1号节点和2号节点相连，
2号节点和4号节点相连，3号节点和4号节点相连，
1号节点和3号节点相连，
若想必须保证相邻两个节点不能同时为红色，总共7种方案。

示例2

输入：
3 3
1 2
1 3
2 3

输出：
4

示例3

输入：
4 3
1 2
2 3
3 4

输出：
8

示例4

输入：
4 3
1 2
1 3
2 3

输出：
8

题解

题目类型：

这道题目属于 位运算 和 枚举 类型的题目，结合了图的染色问题，主要通过枚举所有可能的染色方案来判断是否满足约束条件。

解题思路：

1. 题目理解：
   • 给定一个无向图，图中的每个节点要么是红色，要么是黑色，且相邻的两个节点不能同时为红色。
   • 需要计算出图中满足染色条件的所有方案的个数。
2. 枚举所有可能的染色方案：
   • 假设有 m 个节点，那么可以用一个二进制数表示所有节点的颜色方案。
     • 二进制数的每一位表示一个节点的颜色（0 为黑色，1 为红色）。
     • 例如，对于 m = 3，染色方案可以是：
       • 000（黑色、黑色、黑色）
       • 001（黑色、黑色、红色）
       • 010（黑色、红色、黑色）
       • 111（红色、红色、红色）等。
3. 检查染色是否合法：
   • 对于每一个染色方案，检查是否满足相邻节点不能同时为红色的约束。
   • 如果满足条件，则增加计数。
4. 算法实现：
   • 使用一个二进制数表示每一个染色方案，遍历从 0 到 2^m - 1 的所有可能的方案。
   • 对每一个染色方案，通过位运算提取节点的颜色，检查相邻节点的颜色是否满足条件。

代码大致描述：

1. 输入：
   • 输入包括节点数 m 和边数 n，接着输入 n 条边，每条边表示一对相邻的节点。
2. 检查染色方案的有效性：
   • 对于每个染色方案，检查相邻的节点是否满足约束：即相邻两个节点不能同时为红色（即二进制表示中对应位不能同时为1）。
3. 输出：
   • 输出符合要求的染色方案的个数。

时间复杂度：

• 时间复杂度：

  • 我们枚举所有的染色方案，染色方案的总数为 2^m（即 1 << m）。

  • 对于每一个染色方案，我们需要检查所有的边（即 n 条边），对于每条边，需要进行常数时间的操作（位运算）。因此，时间复杂度为：

    • 由于 m 最大为 15，因此 2^m 最多为 32768，n 最大为 m * 3 = 45，所以时间复杂度在最坏情况下是 ，即最多约为 1.5 million 次操作，足够在合理时间内完成。

• 空间复杂度：

• 存储图的边需要 O(n) 的空间。

  • 存储染色方案和结果需要 O(1) 空间，除去输入和输出。

• 因此，空间复杂度是 O(n)。

C++

#include <bits/stdc++.h>

using namespace std;

bool check(vector<pair<int, int>> &edges, int plan) {
    //举例： plan 3（二进制：0011） 表示 1,2 号节点为红色, 3,4 号节点黑色
    for (const auto [v1, v2]: edges) {
        int c1 = (plan >> (v1 - 1)) & 1;  // 找到第 v1 为的染色值
        int c2 = (plan >> (v2 - 1)) & 1;  // 找到第 v2 为的染色值
        // 必须保证相邻两个节点不能同时为红色
        if (c1 + c2 == 2) return false;
    }

    return true;
}

int main() {
    int m, n;
    cin >> m >> n;
    // 读取 n 条  V1 到 V2 的边， 存储到 edges
    vector<pair<int, int>> edges(n);
    for (int i = 0; i < n; i++) {
        cin >> edges[i].first >> edges[i].second;
    }

    int count = 0;
    // 用二进制位来枚举所有的染色情况，然后统计可行的染色计划
    for (int plan = 0; plan <= (1 << m) - 1; plan++) {
        if (check(edges, plan)) count++;
    }

    cout << count << endl;

    return 0;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏