N0035. 20260603-资源二分类隔离判定

中等

通过率 48% · 提交 27 · 通过 13

200分华为ODDFSBFS

本题改编自算法机考高频题型 · 考点：200分 / 华为OD · 难度：中等

实现一段调度模块功能，将一批资源单元划分到两个隔离资源池中；某些资源单元之间存在互斥关系，例如会竞争同一段频谱、同一类加速卡、同一条转发链路，或者在同一资源池内运行会造成调度冲突；现在有多组资源部署任务，其中第组任务中： - 有 resourceCount[i] 个资源单元，资源编号从1 到 resourceCount[i]；例如 resourceCount[i] 为4时，表示有4个资源，分别为资源1,2,3,4； - conflicts[i] 表示第组任务的互斥资源对，不能放入同一个资源池；例如conflicts[i] 为 [(1,2),(1,3)] 时，表示资源1和资源2互斥，资源1和资源3互斥；请你判断每一组资源部署任务是否可以被划分到两个隔离资源池中，使得每一对互斥资源都位于不同资源池。对于每一组任务： - 如果可以完成划分，返回1。 - 如果无法完成划分，返回0。最终返回一个数组，其中第i个值表示第i组任务是否可以被两个资源池完全隔离。补充说明（约束条件）： 1. 1 <= resourceCount.length <= 100 2. 1 <= resourceCount[i] <= 10^4 3. 0 <= conflicts[i].length <= 2 * 10^4 4. 1 <= conflicts[i][x], conflicts[i][y] <= resourceCount[i] 5. 所有 resourceCount[i] 之和不超过 10^5 6. 所有 conflicts[i].length 之和不超过 2 * 10^5

这类题属于算法机考高频题型中「200分 / 华为OD」方向的高频题型，通常考察对「200分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

resourceCount int整型一维数组每一组的资源总数 conflicts int整型二维数组每一组的互斥资源对，每个元素为[u, v]表示u和v互斥

输出描述

最终返回一个数组，其中第 i 个值表示第 i 组任务是否可以被两个资源池完全隔离。

示例

示例 1

输入示例

3
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 = [(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

输入示例

3
2,2,4
1,2

1,2 2,3 3,4 4,1

输出示例

1,1,1

说明：- 第 1 组任务没有冲突，可以划分。 - 第 2 组任务中资源 1 和资源 2 分别放入不同资源池即可。 - 第 3 组任务形成偶数环，可以被两个资源池隔离。

示例 3

输入示例

2
3,4
1,1
1,2 2,3 3,1

输出示例

0,0

说明：- 第 1 组任务中资源 1 与自己冲突，无法划分。 - 第 2 组任务中资源 1、2、3 形成奇数环，无法只用两个资源池隔离。

时间限制 1000 ms · 内存限制 256 MB

兄师兄答疑 · 训练营专属了解 →

题库上一题下一题

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List
from collections import deque, defaultdict

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param resourceCount int整型一维数组 每一组的资源总数
# @param conflicts int整型三维数组 每一组的互斥资源对，每个元素为[u, v]表示u和v互斥
# @return int整型一维数组
#
class Solution:
    def canPartition(self, resourceCount: List[int], conflicts: List[List[List[int]]]) -> List[int]:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写
if __name__ == "__main__":
    n = int(input().strip())
    resourceCount = list(map(int, input().strip().split(',')))
    conflicts = []
    for _ in range(n):
        line = input().strip()
        if line == "":
            conflicts.append([])
        else:
            pairs = line.split()
            group = []
            for p in pairs:
                u, v = map(int, p.split(','))
                group.append([u, v])
            conflicts.append(group)
    sol = Solution()
    result = sol.canPartition(resourceCount, conflicts)
    print(','.join(map(str, result)))

from typing import List
from collections import deque, defaultdict

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param resourceCount int整型一维数组 每一组的资源总数
# @param conflicts int整型三维数组 每一组的互斥资源对，每个元素为[u, v]表示u和v互斥
# @return int整型一维数组
#
class Solution:
    def canPartition(self, resourceCount: List[int], conflicts: List[List[List[int]]]) -> List[int]:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写
if __name__ == "__main__":
    n = int(input().strip())
    resourceCount = list(map(int, input().strip().split(',')))
    conflicts = []
    for _ in range(n):
        line = input().strip()
        if line == "":
            conflicts.append([])
        else:
            pairs = line.split()
            group = []
            for p in pairs:
                u, v = map(int, p.split(','))
                group.append([u, v])
            conflicts.append(group)
    sol = Solution()
    result = sol.canPartition(resourceCount, conflicts)
    print(','.join(map(str, result)))

写完代码点「提交」，将对全部测试用例判题。