资源二分类隔离判定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 1001 resourceCount[i] 1040 conflicts[i].length 2∗1041 conflicts[i][x],conflicts[i][y] resourceCount[i]5.所有 resourceCount[i] 之和不超过 1056.所有 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依次类推。如果在遍历过程中发现相邻顶点颜色相同则存在奇环不是二分图。特殊情况自环资源与自身互斥无论如何分配都无法满足两个资源池的约束。奇环三个或更多顶点形成闭环顶点个数为奇数无法用两种颜色交替染色。复杂度分析时间复杂度O(N E)其中 N 为资源总数E 为互斥关系总数。空间复杂度O(N E)用于存储邻接表和