如何从多个向量中找到不相同的元素？

Question

给定几个向量/集合,每个向量/集合包含在一个向量内不同的多个整数.现在我想检查是否存在通过从每个给定的向量/集中仅提取一个元素而组成的集合,同时提取的数字彼此不相同.

例如,给定a,b,c,d为:

a <- (1,3,5); 
b <- (3,6,8); 
c <- (2,3,4); 
d <- (2,4,6)

我可以找到像(1,8,4,6)或(3,6,2,4)这样的集合......实际上,我只需要找出一个这样的集合来证明存在.

应用残酷力搜索,可以检查最大m ^ k个组合,其中m是给定集合的大小,k是给定集合的数量.

有没有更聪明的方法？谢谢!

Answer 1

您可以将问题重新表述为二分图中的匹配:

• 左边的节点是你的集合,
• 右侧的节点是出现在集合中的整数.

如果集合包含给定的整数,则"set"节点和"integer"节点之间存在边缘.然后,您试图在此二分图中找到匹配:每个集合将与一个整数相关联,并且不会使用两次整数.找到这种匹配的简单算法的运行时间是O(| V || E |),这里是| V | 小于(m + 1)k和| E | 等于mk.所以你有一个O(m ^ 2 k ^ 2)的解决方案.请参阅:二分图中的匹配.

二分匹配算法:

该算法适用于定向图.开始时,所有边缘都从左到右定向.如果它们之间的边缘从右到左定向,则将匹配两个节点,因此在开始时,匹配为空.该算法的目标是找到"增加路径"(或交替路径),即增加匹配大小的路径.

增强路径是有向图中的路径,从不匹配的左节点开始,到不匹配的右节点结束.一旦你有一个扩充路径,你只需要沿着路径翻转所有边缘,增加一个匹配大小的增量.(匹配的大小将增加,因为您还有一个不属于匹配的边.这称为交替路径,因为路径在不属于匹配的边,左到右和属于匹配的边之间交替,右到左.)

以下是您如何找到扩充路径:

1. 所有节点都标记为未访问,
2. 你选择一个未访问和不匹配的左节点,
3. 你进行深度优先搜索,直到找到一个不匹配的正确节点(然后你有一个增强路径).如果找不到不匹配的正确节点,请转到2.

如果找不到扩充路径,则匹配是最佳的.

寻找增广路径具有复杂度O(| E |),并且您最多在min(k,m)次执行此操作,因为最佳匹配的大小以k和m为界.所以对于你的问题,复杂性将是O(mk min(m,k)).

您还可以参阅此参考资料,第1部分,以获得有关校样的更完整说明.