用公共元素合并集合？

Question

我想用公共元素合并集合。例如

input = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]),  frozenset([1,1000]),
             frozenset([100, 200]), frozenset([100, 300, 400])])

结果：

^{pr2}$

实现这一目标的有效方法是什么？在

Answer 1

使用内置的set.union()->；仅包含set.intersection()长度大于0的结果。在

---

解释如何在高层次上实现这个答案。如果你想要一个具体的解决方案，你必须首先表现出你的努力来解决这个问题。在

Answer 2

这是我试过的。首先，我做了一些简单但错误的事情

result = set()
while input:                                                                   
    r = set(input.pop())
    for rr in input.copy():
        if rr & r:                                                  
            input.remove(rr)
            r.update(rr)  
    result.add(frozenset(r))   

这段代码的问题是合并可能无法完成，这取决于input.pop()的顺序。假设input={frozenset([0, 1]), frozenset([2,3]), frozenset([1,2])}并且这三个元素被弹出并以这个赋值顺序循环，然后results={frozenset([0,1,2]), frozenset([2,3])}。在

然后我实现了答案in this post。它首先建立一个新图的邻接列表，每个节点对应于input的一个frozenset元素。如果两个节点（frozensets）共享公共元素，则它们之间存在边。然后利用深度优先图遍历来寻找新图的连通分量。在

^{pr2}$