资源二分类隔离判定

2026-6-4

2026 华为OD机试真题 6月3日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

实现一段调度模块功能，将一批资源单元划分到两个隔离资源池中；某些资源单元之间存在互斥关系，例如会竞争同一段频谱、同一类加速卡、同一条转发链路，或者在同一资源池内运行会造成调度冲突；现在有多组资源部署任务，其中第组任务中: 有resourceCount个资源单元，资源编号从1 到resourceCount[i]；例如resourceCount[］为4时，表示有4个资源，分别为资源1.2.3,4;·conflicts[］表示第组任务的互斥资源对，不能放入同一个资源池；例如conflicts[i］为［(1.2).(1.3)］时，表示资源1和资源2互斥，资源1和资源3互斥；请你判断每一组资源部署任务是否可以被划分到两个隔离资源池中，使得每一对互斥资源都位于不同资源池。对于每一组任务：．如果可以完成划分，返回1。．如果无法完成划分，返回0。最终返回一个数组，其中第i个值表示第i组任务是否可以被两个资源池完全隔离。

2026 华为OD机试真题 6月3日华为OD上机新系统考试真题 100 分题型

补充说明（约束条件）

1 <= resourceCount.length <= 100
1 <= resourceCount[i] <= 104
0 <= conflicts[i].length <= 2∗104
1 <= conflicts[i][x],conflicts[i][y] <= resourceCount[i]

5.所有 resourceCount[i] 之和不超过 105

6.所有 conflicts[i].length 之和不超过 2∗105

示例1

输入

[4,3,5],[(1,2),(1,3),(2,4)],[(1,2),(2,3),(1,3)],[(1,2),(3,4)]

输出

[1,0,1]

说明

第 1 组任务 resourceCount[0] = 4 ，表示有 1,2,3,4 资源， conflicts[0] =[(1,2),(1,3),(2,4)]，表示第 1 组资源 1 和 2 ， 1 和 3 ， 2 和 4 两两互斥，第 1 组任务可以划分，例如：资源池 1 ：[1,4] 资源池 2 ：[2,3]

第 2 组任务无法划分，因为资源 1、2、3 两两互斥，只用两个资源池无法完成隔离。

第 3 组任务可以划分，例如：资源池 1 ：[1,3,5] 资源池 2 ：[2,4]

示例2

输入

[2,2,4],[(1,2)],[],[(1,2),(2,3),(3,4),(4,1)]

输出

[1,1,1]

说明

第 1 组任务没有冲突，可以划分。

第 2 组任务中资源 1 和资源 2 分别放入不同资源池即可。

第 3 组任务形成偶数环，可以被两个资源池隔离。

示例3

输入

[3,4],[(1,1)],[(1,2),(2,3),(3,1)]

输出

[0,0]

说明

第 1 组任务中资源 1 与自己冲突，无法划分。

第 2 组任务中资源 1、2、3 形成奇数环，无法只用两个资源池隔离。

解题思路

本题本质上是判断一个图是否为二分图。

二分图定义：如果能把图中所有顶点分成两个不相交的集合，使得图中每条边的两端分别属于这两个集合，则该图是二分图。
资源隔离映射：互斥的资源对之间必须分配到不同的资源池，即对应图的一条边两端必须异色。
二分图判定：使用染色法 BFS。从某个未染色的顶点开始，将其染成颜色 0，然后将其所有邻居染成颜色 1，依次类推。如果在遍历过程中发现相邻顶点颜色相同，则存在奇环，不是二分图。
特殊情况：
- 自环：资源与自身互斥，无论如何分配都无法满足两个资源池的约束。
- 奇环：三个或更多顶点形成闭环，顶点个数为奇数，无法用两种颜色交替染色。