如何合并具有交集的集合（连通分量算法）？

Question

是否有任何有效的方法来合并具有交集的集合。例如：

l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]

预期的结果是：

r = [{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]

应合并所有具有交集（公共组件）的集合。例如：

{1, 3} & {2, 3}
# {3}

所以这两组应该合并：

{1, 3} | {2, 3}
# {1, 2, 3}

不幸的是，我没有任何可行的解决方案。

更新：结果中集合的顺序并不重要。

Answer 1

实现@mkrieger1 在评论中提到的连通分量算法的一种有效方法是将集合列表转换为一组可散列的frozensets，以便当您遍历它并找到与当前的frozenset 相交的frozenset 时，您可以轻松地从池中删除它：

pool = set(map(frozenset, l))
groups = []
while pool:
    groups.append(set(pool.pop()))
    while True:
        for candidate in pool:
            if groups[-1] & candidate:
                groups[-1] |= candidate
                pool.remove(candidate)
                break
        else:
            break

鉴于l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]，groups将变成：

[{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]

并且给定l = [{1, 2}, {3, 4}, {2, 3}],groups将变成：

[{1, 2, 3, 4}]

并且给定l = [{1}, {2}, {1, 2}],groups将变成：

[{1, 2}]