无向图 - 灯泡

Question

我最近开始学习图形及其不同的遍历算法，似乎无法拿出这个问题的答案。我真的需要你的帮助，我甚至不知道从哪里开始。 P.S.昨天是我的生日，因为这个问题我不想哭。

纽约的一家公司生产汽车用蓝色卤素灯泡。不幸的是，要持续地为灯泡着色是非常困难的。自然地，包装看起来相似的灯泡也是非常重要的。为了将灯泡成对包装，从装配线出来的灯泡首先被分成两组共同类似颜色的灯泡（例如，一组较暗的灯泡，另一组灯泡），然后在每组内形成配对。

由于需求的增加，公司希望雇用更多的员工将灯泡分成两组。为了确定申请人是否具备适当的技能来执行这项相当微妙的任务，他们被要求采取这个简单的测试：给定一组nn灯泡，比较每一对灯泡并确定两个灯泡是否具有“相似”或“不同”颜色。申请人也可以选择对每一对说“不确定”。该公司希望聘用符合判断的申请人。如果可以将n个灯泡分成两组，使得（i）对于被确定为“相似”的每个对{a，b}，a（a），则判断m个判断（导致“相似”或“不同”）是一致的和b确实属于同一集合，并且（ii）对于被确定为“不同”的每对{a，b}，a和b确实属于不同的集合。

对于具有m个判断的n个灯泡的给定测试结果，设计O（n + m）时间算法以确定判断是否一致。在实践中，应该有最低数量的申请人需要作出的判断，但是你的算法应该适用于任何整数m≥0。

非常感谢！

Answer 1

我会做这样的：

1. 与每个灯泡顶点创建一个图表。如果判断结果相同，则用红边连接顶点，如果判断结果不同，则用蓝边连接。

2. 使用DFS，BFS或其他方法将图分区为由红色边连接的顶点集。

3. 检查每个红色连接组件内是否有蓝色边缘。如果是这样，那么判断是不一致的。

4. 将每个红色连接的组件折叠成一个顶点。这将从图形中移除所有红色边缘。由于（3），它不会去除任何蓝色边缘。此操作反映了限制，即将灯泡分为两组时，每个红色连接组件中的所有灯泡必须位于同一组中。

5. 检查结果图是否是双向的。如果是这样，那么你可以一直划分图。否则你不能。

这些步骤中的每一步，如果做得对，都适合O（n + m）时间。