确定集合联合的有效方法

Question

我有一个(非常大的)集合列表,包含一对值,例如:

SetList = [{1,2},{2,3},{4,5},{5,6},{1,7}]

我想有效地确定上述对中关系的传递性所暗示的不相交值集.例如,1与2相关联,2与3相关,因此1,2,3相关联.类似地,1与7相关联,因此1,2,3和7相关联.在上面,4,5和6是相关联的,但不与剩余的值相关联.结果应如下所示:

DisjointSets = [{1,2,3,7},{4,5,6}]

是否有简单而有效的方法来执行我缺少的操作？谢谢!

Answer 1

将我的原始列表转换为元组:

TupleList = [(1,2),(2,3),(4,5),(5,6),(1,7)]

我使用networkx via(感谢@ user2357112):

import networkx as nx
G = nx.path_graph(0)
G.add_edges_from(TupleList)
DisjointSets = list(nx.connected_components(G))

这是解决问题的最有效方法吗？还有其他想法吗？