华为OD机试 - 无向图染色（Java 2024 E卷 100分）

在这里插入图片描述

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

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

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

一、题目描述

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

二、输入描述

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

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

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

三、输出描述

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

说明

0 < n <= 15
0 <= N <= M * 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 3
1 2
1 3
2 3

2、输出

3、说明

3个节点，3条边。所有满足条件的染色方案共有4种。

五、解题思路

邻接表的构建：使用邻接表表示无向图，每个节点存储其相邻节点的列表。
回溯算法：通过回溯遍历所有可能的染色方案。对于每个节点，有两种选择：染为黑色或红色。
染为黑色：无需检查相邻节点，直接递归处理下一个节点。
染为红色：需要检查所有相邻节点是否已经染为红色。如果没有相邻节点染红，则可以染红，并继续递归处理下一个节点。
计数：每当所有节点都被处理完毕且满足条件时，计数加一。

六、Java算法源码

public class OdTest {
    private static int M; // 节点数
    private static int N; // 边数
    private static List<Integer>[] adj; // 邻接表
    private static int count = 0; // 有效染色方案计数

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取节点数M和边数N
        M = scanner.nextInt();
        N = scanner.nextInt();

        // 初始化邻接表
        adj = new ArrayList[M];
        for (int i = 0; i < M; i++) {
            adj[i] = new ArrayList<>();
        }

        // 读取N条边，构建无向图
        for (int i = 0; i < N; i++) {
            int u = scanner.nextInt() - 1; // 节点编号从1开始，转换为0-based
            int v = scanner.nextInt() - 1;
            adj[u].add(v);
            adj[v].add(u);
        }

        // 开始回溯，从第0个节点开始
        backtrack(0, new boolean[M]);

        // 输出有效染色方案的数量
        System.out.println(count);

        scanner.close(); // 关闭扫描器
    }

    /**
     * 回溯函数，用于遍历所有可能的染色方案
     *
     * @param node 当前处理的节点编号
     * @param red  当前已染为红色的节点集合
     */
    private static void backtrack(int node, boolean[] red) {
        // 如果所有节点都已处理，增加计数
        if (node == M) {
            count++;
            return;
        }

        // 尝试将当前节点染为黑色
        backtrack(node + 1, red);

        // 尝试将当前节点染为红色
        boolean canBeRed = true;
        for (int neighbor : adj[node]) {
            if (red[neighbor]) {
                canBeRed = false; // 相邻节点已染红，不能染红
                break;
            }
        }

        if (canBeRed) {
            red[node] = true; // 将当前节点染为红色
            backtrack(node + 1, red);
            red[node] = false; // 回溯，撤销染色
        }
    }
}