会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
题解
题面描述
终端部门为了对穿戴设备进行交叉测试，目前有n名员工投入测试，人员从1到n依次编号。为了充分测试和暴露问题，要求任何两个以前戴过同一穿戴设备的人不能再次测同一设备。下面会给出测试投入的人数和测过同一台设备的人员编号，请按照此关系，计算这次至少需要几台穿戴设备供测试。
解题思路
将员工和他们之前使用相同设备的关系建模为图的顶点和边，通过应用DSATUR图着色算法，为每个员工分配不同的颜色，确保任何两个曾共同使用过设备的员工不会分配到相同的颜色。最终，通过确定所需的最少颜色数，即可得到测试所需的最少穿戴设备数量。
题目内容
终端部门正在组织一次穿戴设备交叉测试，参加测试的员工共有 n 名，编号依次为 1 到 n。测试中需要为这些员工分配穿戴设备，但必须满足一条规则：如果两名员工以前曾经使用过同一台设备，那么本次测试中不能让他们再次使用同一台设备。
已知若干条“曾使用同一台设备”的员工关系记录，请在满足上述规则的前提下，计算本次测试至少需要准备多少台穿戴设备。
约束条件
- 参加测试的员工人数
n 满足 1<n<100。
- 历史上使用过同一台设备的记录条数
m 满足 1≤m≤2n∗(n−1)。
