python - 改进寻找最小生成树的实现

我试图实现kruskal的算法，在python中找到一个最小生成树来解决在线判断问题，但是我遇到了时间限制问题。这个问题以递增的顺序给出一系列边，并询问是否可能有最小生成树。可以看到完整的问题规范here.
这是我的问题代码：

import sys
raw_input = sys.stdin.readline
line = map(int, raw_input().split())
n = line[0]
m = line[1]
dict1 = {}
lists = []

for i in xrange(1, n + 1):
    dict1[i] = set([i])

for i in xrange(m):
    edge = map(int, raw_input().split())
    a = edge[0]
    b = edge[1]
    if dict1[a] != dict1[b]:
        newSet = dict1[a].union(dict1[b])
        for vertice in newSet:
            dict1[num] = newSet
        lists.append(i + 1)

check = all(dict1[x] == dict1[1] for x in dict1.keys())

if check:
    for i in lists:
        print i
else:
    print "Disconnected Graph"

代码首先为所有可能的顶点创建不相交集。然后，对于每个边，它检查两个顶点所在的集是否不同如果它们是，那么这两个集合将与联合操作结合起来。组合集中的每个顶点都是新创建的组合集中的成员如果顶点已连接，则跳过它们我认为我的代码的问题在于行中必须更新集合的次数：

for vertice in newSet:
    dict1[num] = newSet

有没有更快的方法来更新集合以检查它们是否相等？这个操作大约取O（顶点^ 2）的时间，并且当有多达100000个顶点时需要花费太长时间。

最佳答案

关键是要为集合使用适当的数据结构合并节点集并测试两个节点是否在同一集中是一个经典的计算机科学问题，称为“联合查找”。
最好的数据结构很简单，如下所述：
http://www.algorithmist.com/index.php/Union_Find
使用这种结构，您可以合并集合并在非常恒定的时间内测试相等性，这使得您对Kruskal算法的实现（这里提供了预排序的边列表）非常线性。