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

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

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+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、输出

7

3、说明

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

测试用例2：

1、输入

3 0

2、输出

8

3、说明

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

五、解题思路

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

数据结构与算法选择

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

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

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

六、Java算法源码

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

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

        // 初始化邻接表，使用位掩码表示
        int[] adjacency = new int[M];

        // 读取N条边，并构建邻接表
        for (int i = 0; i < N; i++) {
            int V1 = scanner.nextInt() - 1; // 转为0-based索引
            int V2 = scanner.nextInt() - 1;
            adjacency[V1] |= (1 << V2);
            adjacency[V2] |= (1 << V1);
        }

        scanner.close();

        int count = 0;
        int total = 1 << M; // 2^M种染色方案

        // 遍历所有可能的染色方案
        for (int s = 0; s < total; s++) {
            boolean 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++;
            }
        }

        // 输出结果
        System.out.println(count);
    }
}

七、效果展示

1、输入

2 1
1 2

2、输出

3

3、说明

有两个节点和一条边：

都染黑
节点1染红，节点2染黑
节点1染黑，节点2染红 共3种方案。

🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）

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

原文地址：https://blog.csdn.net/guorui_java/article/details/142697618

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！