无向图染色
题目描述
给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
输入描述
第一行输入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
题解
题目类型：
这道题目属于 位运算 和 枚举 类型的题目，结合了图的染色问题，主要通过枚举所有可能的染色方案来判断是否满足约束条件。
解题思路：
- 题目理解：
- 给定一个无向图，图中的每个节点要么是红色，要么是黑色，且相邻的两个节点不能同时为红色。
- 需要计算出图中满足染色条件的所有方案的个数。
- 枚举所有可能的染色方案：
- 假设有
m个节点，那么可以用一个二进制数表示所有节点的颜色方案。
- 二进制数的每一位表示一个节点的颜色（0 为黑色，1 为红色）。
- 例如，对于
m = 3，染色方案可以是：
000（黑色、黑色、黑色）001（黑色、黑色、红色）010（黑色、红色、黑色）111（红色、红色、红色）等。- 检查染色是否合法：
- 对于每一个染色方案，检查是否满足相邻节点不能同时为红色的约束。
- 如果满足条件，则增加计数。
- 算法实现：
- 使用一个二进制数表示每一个染色方案，遍历从
0到2^m - 1的所有可能的方案。- 对每一个染色方案，通过位运算提取节点的颜色，检查相邻节点的颜色是否满足条件。
代码大致描述：
- 输入：
- 输入包括节点数
m和边数n，接着输入n条边，每条边表示一对相邻的节点。- 检查染色方案的有效性：
- 对于每个染色方案，检查相邻的节点是否满足约束：即相邻两个节点不能同时为红色（即二进制表示中对应位不能同时为1）。
- 输出：
- 输出符合要求的染色方案的个数。
时间复杂度：
时间复杂度：
我们枚举所有的染色方案，染色方案的总数为
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;
}
#面经##春招##秋招##华为od##C++#整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
C++笔试真题题解 文章被收录于专栏
笔试真题题解
