当前位置：首页 > news >正文

华为OD机试 - 无向图染色（Python/JS/C/C++ 2024 E卷 100分）

news 2025/5/5 1:44:23

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

二、输入描述

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

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

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

三、输出描述

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

说明

0 < N < 15
0 <= M <= N * 3
0 <= s, t < n

不保证图连通
保证没有重边和自环

四、测试用例

测试用例1：

1、输入

4 4
1 2
2 4
3 4
1 3

2、输出

3、说明

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

测试用例2：

1、输入

3 0

2、输出

3、说明

没有任何边，所有节点可以自由染色。每个节点有2种选择，总共2^3=8种方案。

五、解题思路

题目要求在一个无向图中，用红色和黑色两种颜色对节点进行染色，且相邻的两个节点不能同时为红色。我们需要计算满足条件的不同染色方案的总数。

数据结构与算法选择

邻接表（Adjacency List）：由于节点数较小（M ≤ 15），可以使用一个整数数组 adjacency 来表示每个节点的邻接关系。每个元素 adjacency[i] 用二进制位来表示节点 i 的邻居，方便进行位运算。

枚举所有子集（Bitmasking）：由于节点数不超过15，可以通过枚举所有可能的节点子集（即所有可能的染色方案）来解决问题。每个子集对应一种将某些节点染为红色，其余染为黑色的方案。

验证独立集：对于每个子集，检查其中是否存在相邻的两个节点都被染为红色。如果不存在，则该子集对应的染色方案是有效的。

六、Python算法源码

# Python 代码实现
import sysdef main():import sysimport math# 读取输入的所有内容并按行分割input = sys.stdin.read().split()idx = 0# 读取节点数M和边数NM = int(input[idx])idx += 1N = int(input[idx])idx += 1# 初始化邻接表，使用位掩码表示每个节点的邻居adjacency = [0] * M# 读取N条边，并构建邻接表for _ in range(N):V1 = int(input[idx]) - 1  # 转为0-based索引idx += 1V2 = int(input[idx]) - 1idx += 1adjacency[V1] |= (1 << V2)  # 将V2加入V1的邻居adjacency[V2] |= (1 << V1)  # 将V1加入V2的邻居# 初始化有效染色方案的计数count = 0total = 1 << M  # 计算2^M种染色方案# 遍历所有可能的染色方案for s in range(total):valid = True  # 标记当前方案是否有效for i in range(M):if ((s >> i) & 1) == 1:  # 如果节点i被染为红色if (s & adjacency[i]) != 0:  # 检查相邻节点是否也被染为红色valid = False  # 当前方案无效break  # 跳出内层循环if valid:count += 1  # 有效方案计数加一# 输出结果print(count)# 调用主函数
if __name__ == "__main__":main()

七、JavaScript算法源码

// JavaScript 代码实现
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];
rl.on('line', function(line){input = input.concat(line.trim().split(/\s+/));
}).on('close', function(){let idx = 0;// 读取节点数M和边数Nconst M = parseInt(input[idx++]);const N = parseInt(input[idx++]);// 初始化邻接表，使用位掩码表示每个节点的邻居const adjacency = new Array(M).fill(0);// 读取N条边，并构建邻接表for(let i = 0; i < N; i++){const V1 = parseInt(input[idx++]) - 1; // 转为0-based索引const V2 = parseInt(input[idx++]) - 1;adjacency[V1] |= (1 << V2); // 将V2加入V1的邻居adjacency[V2] |= (1 << V1); // 将V1加入V2的邻居}let count = 0;const total = 1 << M; // 计算2^M种染色方案// 遍历所有可能的染色方案for(let s = 0; s < total; s++){let valid = true; // 标记当前方案是否有效for(let i = 0; i < M; i++){if( ((s >> i) & 1) === 1 ){ // 如果节点i被染为红色if( (s & adjacency[i]) !== 0 ){ // 检查相邻节点是否也被染为红色valid = false; // 当前方案无效break; // 跳出内层循环}}}if(valid){count++; // 有效方案计数加一}}// 输出结果console.log(count);
});

八、C算法源码

// C 语言代码实现
#include <stdio.h>int main(){int M, N;// 读取节点数M和边数Nif(scanf("%d %d", &M, &N)!=2){return 0;}// 初始化邻接表，使用位掩码表示每个节点的邻居int adjacency[M];for(int i=0;i<M;i++){adjacency[i] = 0;}// 读取N条边，并构建邻接表for(int i=0;i<N;i++){int V1, V2;if(scanf("%d %d", &V1, &V2)!=2){return 0;}V1 -= 1; // 转为0-based索引V2 -= 1;adjacency[V1] |= (1 << V2); // 将V2加入V1的邻居adjacency[V2] |= (1 << V1); // 将V1加入V2的邻居}int count = 0;int total = 1 << M; // 计算2^M种染色方案// 遍历所有可能的染色方案for(int s=0; s < total; s++){int valid = 1; // 标记当前方案是否有效for(int i=0; i < M; i++){if( ((s >> i) & 1) == 1 ){ // 如果节点i被染为红色if( (s & adjacency[i]) != 0 ){ // 检查相邻节点是否也被染为红色valid = 0; // 当前方案无效break; // 跳出内层循环}}}if(valid){count++; // 有效方案计数加一}}// 输出结果printf("%d\n", count);return 0;
}

九、C++算法源码

// C++ 代码实现
#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int M, N;// 读取节点数M和边数Ncin >> M >> N;// 初始化邻接表，使用位掩码表示每个节点的邻居vector<int> adjacency(M, 0);// 读取N条边，并构建邻接表for(int i=0; i<N; i++){int V1, V2;cin >> V1 >> V2;V1 -= 1; // 转为0-based索引V2 -= 1;adjacency[V1] |= (1 << V2); // 将V2加入V1的邻居adjacency[V2] |= (1 << V1); // 将V1加入V2的邻居}int count = 0;int total = 1 << M; // 计算2^M种染色方案// 遍历所有可能的染色方案for(int s=0; s < total; s++){bool valid = true; // 标记当前方案是否有效for(int i=0; i < M; i++){if( ((s >> i) & 1) == 1 ){ // 如果节点i被染为红色if( (s & adjacency[i]) != 0 ){ // 检查相邻节点是否也被染为红色valid = false; // 当前方案无效break; // 跳出内层循环}}}if(valid){count++; // 有效方案计数加一}}// 输出结果cout << count << "\n";return 0;
}