【100%通过率】华为OD机试真题2026双机位C卷 C++ 实现【红黑图】

目录

题目

思路

Code

题目

众所周知红黑树时一种平衡树，它最突出的特性就是不能有两个相连的红色节点。那我们定义一个红黑图，也就是一张无向图中，每个节点可能是红黑两种颜色，但我们保证没有两个相邻的红色节点。
现在给一张未染色的无向图，只能染红黑两种颜色，问总共有多少种染色方案使得它成为一个红黑图。
输入描述
第一行输入M(图中节点数)N(边数)
后续N行格式为:V1V2表示一个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

思路

1：数据范围比较小，因此可以考虑暴力破解的方式。

2：图类似的题目，基本就是考察节点和边的处理方式。