题目内容

终端部门为了对穿戴设备进行交叉测试，目前有$n$名员工投入测试，人员从$1$到$n$依次编号。为了充分测试和暴露问题，要求任何两个以前戴过同一穿戴设备的人不能再次测同一设备。下面会给出测试投入的人数和测过同一台设备的人员编号，请按照此关系，计算这次至少需要几台穿戴设备供测试

输入描述

第一行，一个整数$n(1<n<100)$，表示参加测试的人数，人员从$1$到$n$依次编号。

题解

题面描述

终端部门为了对穿戴设备进行交叉测试，目前有$n$名员工投入测试，人员从$1$到$n$依次编号。为了充分测试和暴露问题，要求任何两个以前戴过同一穿戴设备的人不能再次测同一设备。下面会给出测试投入的人数和测过同一台设备的人员编号，请按照此关系，计算这次至少需要几台穿戴设备供测试。

解题思路

将员工和他们之前使用相同设备的关系建模为图的顶点和边，通过应用DSATUR图着色算法，为每个员工分配不同的颜色，确保任何两个曾共同使用过设备的员工不会分配到相同的颜色。最终，通过确定所需的最少颜色数，即可得到测试所需的最少穿戴设备数量。