algorithm - 无向图 - 灯泡

Question

我最近开始研究图及其不同的遍历算法，似乎无法得出这个问题的答案。我真的需要你的帮助，我什至不知道从哪里开始。附言昨天是我的生日，我不想因为这个问题而哭。

纽约的一家公司生产汽车用蓝色卤素灯泡。不幸的是，很难始终如一地给灯泡上色。当然，将外观相似的灯泡成对包装也很重要。为了成对包装灯泡，首先将装配线出来的灯泡分成两组颜色相似的灯泡(例如，一组较暗的灯泡，另一组较浅的灯泡)，然后在每组内形成对。

由于需求增加，该公司希望雇用更多 worker 将灯泡分成两组。为了确定申请人是否具备执行这项相当精细的任务的适当技能，他们被要求进行以下简单测试:给定一组 nn 个灯泡，比较每对灯泡并确定两个灯泡的颜色是“相似”还是“不同”。申请人还可以选择对每一对说“不确定”。公司希望聘用判断力一致的求职者。我们说 m 个判断(导致“相似”或“不同”)是一致的，如果可以将 n 个灯泡分成两组，使得 (i) 对于每一对 {a,b} 被确定为“相似”，a和 b 确实属于同一集合，并且 (ii) 对于确定为“不同”的每一对 {a,b}，a 和 b 确实属于不同的集合。

对于给定的 n 个灯泡的测试结果，m 个判断，设计一个 O(n+m) 时间的算法来判断判断是否一致。在实践中，应要求申请人做出最少数量的判断，但你的算法应该适用于任何整数 m≥0。

非常感谢!

Answer 1

我会这样做:

1. 为每个灯泡创建一个顶点图。判断相同时用红色边连接顶点，判断不同时用蓝色边连接顶点。

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

3. 检查每个红色连接的组件中是否有任何蓝色边缘。如果是，则判断不一致。

4. 将每个红色连接的组件折叠成一个顶点。这将从图中删除所有红色边缘。由于 (3)，它不会删除任何蓝色边缘。此操作反射(reflect)了这样的限制，即当您将灯泡分成两组时，每个红色连接组件中的所有灯泡都必须属于同一组。

5. 检查结果图是否是二分图。如果是这样，那么您可以一致地划分图形。否则你不能。

如果正确执行，这些步骤中的每一步都适合 O(n+m) 时间。