0

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

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

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

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

太感谢了！

4

1 回答 1

1

我会这样做：

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

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

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

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

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

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

于 2017-02-13T13:37:54.540 回答