解题思路
每组任务在资源 1…n 上建无向图:互斥对即边。两个资源池对应图的二染色(二分划分):同色可同池,异色必须分池。
判定步骤(对每组独立):
- 自环:若存在 (u,u),直接不可行(同一资源不能与自己互斥又同池)。
- 二分图判定:对尚未染色的连通块 BFS/DFS 染色。若发现相邻同色,说明存在奇环,不可行;否则可行。
- 无边或仅孤立点:任意划分均可,输出
1。
P14393.资源二分类隔离判定(200分)
题目内容
最终返回一个数组,其中第 i 个值表示第 i 组任务是否可以被两个资源池完全隔离。
补充说明(约束条件)
1. 1 <= resourceCount.length <= 100
2. 1 <= resourceCount[i] <= 104
3. 0 <= conflicts[i].length <= 2∗104
4. 1 <= conflicts[i][x],conflicts[i][y] <= resourceCount[i]
5.所有 resourceCount[i] 之和不超过 105
6.所有 conflicts[i].length 之和不超过 2∗105
题意:每组给出资源总数 resourceCnt 、互斥资源对 conflicts ,互斥的两个资源不能放入同一个资源池;判断全部资源能否仅使用两个资源池完成划分,可行填 1 ,不可行填 0 。本质等价:互斥关系构成的图是否是二分图(不能自环、不能存在奇数环)。
样例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 形成奇数环,无法只用两个资源池隔离。