每组任务在资源 1…n 上建无向图:互斥对即边。两个资源池对应图的二染色(二分划分):同色可同池,异色必须分池。
判定步骤(对每组独立):
1。最终返回一个数组,其中第 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 。本质等价:互斥关系构成的图是否是二分图(不能自环、不能存在奇数环)。
输入
[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,4],[(1,2)],[],[(1,2),(2,3),(3,4),(4,1)]
输出
[1,1,1]
说明
第 1 组任务没有冲突,可以划分。
第 2 组任务中资源 1 和资源 2 分别放入不同资源池即可。
第 3 组任务形成偶数环,可以被两个资源池隔离。
输入
[3,4],[(1,1)],[(1,2),(2,3),(3,1)]
输出
[0,0]
说明
第 1 组任务中资源 1 与自己冲突,无法划分。
第 2 组任务中资源 1、2、3 形成奇数环,无法只用两个资源池隔离。