网硕互联帮助中心最新华为OD机试
真题目录：点击查看目录 华为OD面试真题精选：点击立即查看
题目描述
给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
输入描述
第一行输入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
输入
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
说明
解题思路
要解决这个图的染色问题，我们可以利用深度优先搜索（DFS）进行递归遍历每一个节点，对于每个节点，我们可以选择将其染为红色或黑色，同时要注意相邻节点的限制条件。
步骤分析:
输入处理： 读取节点数 M 和边数 N。然后将接下来的 N 行表示为无向边存储在一个二维布尔数组中, 这个数组可以表示图的邻接矩阵。
DFS 递归函数设计：
- 定义一个递归函数 dfs，它接受当前节点索引、上次染红的节点（通过位运算表示），以及图的邻接矩阵作为参数。
- 如果当前节点的索引超过 M，说明染色完成，返回1（表示成功的一种方案）。
染色决策：
- 染黑色: 在每次调用 DFS 时，首先尝试将当前节点染色为黑色，不需要进行任何检查，直接继续到下一个节点。
- 染红色: 对于染红色的情况，需要检查当前节点的邻接节点是否已经被染为红色。通过位运算判断当前节点的邻接节点的状态。
- 通过检查邻接矩阵和红色节点的状态，确定当前节点是否可以染红。
- 如果可以染红，将其
评论前必须登录！
注册