2023年华为OD机考真题：红黑图

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：红黑图
知识点枚举
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
众所周知红黑树是一种平衡树，它最突出的特性就是不能有两个相邻的红色节点。
那我们定义一个红黑图，也就是一张无向图中，每个节点可能有红黑两种颜色，但我们必须保证没有两个相邻的红色节点。
现在给出一张未染色的图，只能染红黑两色，问总共有多少种染色方案使得它成为一个红黑图。
输入描述：
第一行两个数字n m，表示图中有n个节点和m条边。
接下来共计m行，每行两个数字s t，表示一条连接节点s和节点t的边，节点编号为[0,n)。
输出描述：
一个数字表示总的染色方案数。
补充说明：
0 < n < 15
0 <= m <= n * 3
0 <= s, t < n
不保证图连通
保证没有重边和自环
示例1
输入：
3 3
0 1
0 2
1 2
输出：
4
示例2
输入：
4 3
0 1
1 2
2 3
输出：
8
示例3
输入：
4 3
0 1
0 2
1 2
输出：
8
解题思路：
求出红黑图所有的配色方案。方案总个数2^n。
遍历配色方案是否符合无相邻红色，如不符合则从总数中-1。

代码实现：Java代码满分实现

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @title 红黑图
 * @Description 众所周知红黑树是一种平衡树，它最突出的特性就是不能有两个相邻的红色节点。
 * 那我们定义一个红黑图，也就是一张无向图中，每个节点可能有红黑两种颜色，但我们必须保证没有两个相邻的红色节点。
 * 现在给出一张未染色的图，只能染红黑两色，问总共有多少种染色方案使得它成为一个红黑图。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<int[]> list = new ArrayList<>();   //相连的节点数组集合
        for (int i = 0; i < m; i++) {
            int[] points = new int[2];
            points[0] = sc.nextInt();
            points[1] = sc.nextInt();
            list.add(points);
        }

        int total = (int) Math.pow(2, n);   //n个节点有2^n个红黑搭配
        int res = total;
        for (int i = 0; i < total; i++) {
            int temp = i;
            int[] ints = new int[n];    //红黑搭配的情况（0表示红，1表示黑）
            for (int j = 0; j < n; j++) {
                ints[j] = temp % 2;
                temp /= 2;
            }
            for (int[] points : list) {
                if (ints[points[0]] == 0 && ints[points[1]] == 0) {   //相连的节点都是红色，表示不符合
                    res--;
                    break;  //任意一个相连不符则表示此情况不符合
                }
            }
        }
        System.out.println(res);
    }
}