找到一对没有交集的对

Given a set of n pairs of integers, is there a fast way to determine if there exists two pairs (x₁, y₁) and (x₂, y₂) so that the intersection of the sets {x₁, y₁} and {x₂, x₂} is empty?

例如，{(0,1), (0,2), (2,1), (3,2)} 的答案为 {(0,1), (3,2)}。然而{(0,1),(0,2),(2,1)}没有这样的对。

在 Python 中，您可以按如下方式尝试所有对。

l = [(0,1), (0,2), (2,1), (3,2)]
print  [pairs for pairs in itertools.combinations(l, 2)
    if not (set(pairs[0]) & set(pairs[1]))]

This approach takes O(n²) time. Can you get something closer to linear time?

以下算法应该在 O(n) 时间内运行。它基于以下观察：如果你有一对 {a, b}，那么每隔一对

1. 不包括 a 或 b，或者
2. 至少包括 a 或 b 之一。

如果您选择任何集合 {a, b} 并将每个其他集合分类为这五个类别之一，请注意，如果您在情况 1 中得到任何内容，那么您就完成了并且您知道存在这样一个对。因此，唯一有趣的情况是当所有其他集合都属于情况 2 时。当这种情况发生时，我们可以将这两个组称为“A”组和“B”组（对于匹配 a 的集合和与 b 匹配的集合）。

一旦你有了A组和B组，你就知道没有两个A集合可以成为你想要的对，没有两个B集合可以成为你想要的对，并且集合{a，b}不能成为其中的一部分你想要的那对。唯一的选择是，您可以将 A 组中的某些内容与 B 组中的某些内容配对。仅当 A 组中的某些非 A 组件与 B 组中的任何非 B 组件不匹配时，才会发生这种情况。您可以在 O(n) 中检查这一点，方法是构建一个包含 A 组的非 A 组件的哈希表，然后检查 B 组的每个元素其非 B 组件是否在哈希集中。

总而言之，该算法是

• 选择一对 {a, b}。
• For each other pair {c, d}:
  • 如果 {a, b} 和 {c, d} 不相交，则完成。
  • 否则，如果 {a, b} = {c, d}，则丢弃 {c, d}。
  • 否则，如果包含 a，则将 {c, d} 放入 A 组；如果包含 b，则将其放入 B 组。
• 如果 A 组或 B 组中有一个为空，则不存在对。返回假。
• 对于 A 组的每个元素，将该对的非元素添加到哈希集中。
• 如果 B 组的任何元素具有不在哈希集中的非 b 分量，则返回 true，否则返回 false。

其运行时间为 O(n) 并使用 O(n) 额外内存。

希望这可以帮助！