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

目录题目思路Code题目众所周知红黑树时一种平衡树它最突出的特性就是不能有两个相连的红色节点。那我们定义一个红黑图也就是一张无向图中每个节点可能是红黑两种颜色但我们保证没有两个相邻的红色节点。现在给一张未染色的无向图只能染红黑两种颜色问总共有多少种染色方案使得它成为一个红黑图。输入描述第一行输入M(图中节点数)N(边数)后续N行格式为:V1V2表示一个V1到V2的边。数据范围:1M15.0NM*3不能保证所有节点都是连通的。保证没有重边和自环。输出描述输出一个数字表示染色方案的个数示例1输入4 41 22 43 41 3输出7说明4个节点4条边1号节点和2号节点相连2号节点和4号节点相连3号节点和4号节点相连1号节点和3号节点相连若想必须保证相邻两个节点不能同时为红色总共7种方案。示例2输入3 31 21 32 3输出4思路1数据范围比较小因此可以考虑暴力破解的方式。2图类似的题目基本就是考察节点和边的处理方式。节点的表达方式int - 二进制数字。举例1 10001011表示红色0表示黑色边的表达方式ArrayListint 只有两个元素 表示两个节点之间相连存到数组中。3有了节点和边直接遍历所有的可能表达方式即可其实有点暴力遍历的意思。Codeimport java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int m in.nextInt(); // 节点数 int n in.nextInt(); // 边数 // 读入所有边edges[i] {u, v} int[][] edges new int[n][2]; for (int i 0; i n; i) { edges[i][0] in.nextInt(); edges[i][1] in.nextInt(); } int count 0; // 状态压缩枚举用 m 位二进制表示每个节点的颜色1红0黑 // 总共 2^m 种染色方案逐一检查合法性 for (int state 0; state (1 m); state) { boolean valid true; // 检查每条边如果两端节点都是红色则该方案不合法 for (int j 0; j n; j) { int u edges[j][0]; // 边的一端 int v edges[j][1]; // 边的另一端 // 取出节点 u 和 v 在当前状态中对应的颜色位 boolean uRed ((state (m - u)) 1) 1; boolean vRed ((state (m - v)) 1) 1; if (uRed vRed) { valid false; break; } } if (valid) count; } System.out.println(count); } }Gopackage main import ( bufio fmt os ) func main() { reader : bufio.NewReader(os.Stdin) var m, n int fmt.Fscan(reader, m, n) // 节点数、边数 // 读入所有边edges[i] {u, v} edges : make([][2]int, n) for i : 0; i n; i { fmt.Fscan(reader, edges[i][0], edges[i][1]) } count : 0 // 状态压缩枚举用 m 位二进制表示每个节点的颜色1红0黑 // 总共 2^m 种染色方案逐一检查合法性 for state : 0; state (1 m); state { valid : true // 检查每条边如果两端节点都是红色则该方案不合法 for j : 0; j n; j { u : edges[j][0] // 边的一端 v : edges[j][1] // 边的另一端 // 取出节点 u 和 v 在当前状态中对应的颜色位 uRed : ((state (m - u)) 1) 1 vRed : ((state (m - v)) 1) 1 if uRed vRed { valid false break } } if valid { count } } fmt.Println(count) }【华为od机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群830285880】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗?有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。