edge = [[1,2,1],[1,2,3],[1,3,2],[2,3,1],[2,4,4],[3,4,2]]
#这是用边集合表示的图
s = [[]]
n = 4
for i in range(n):
s.append([i+1])
#print s
#compare方法是为了对边排序写的,作为参数传入sort,就可以排序了
def compare(a,b):
if(a[2] > b[2]):
return 1
elif(a[2] < b[2]):
return -1
else:
return 0
edge.sort(compare)
#这就是sort()的厉害之处
for e in edge:
# print s
if s[e[0]] != s[e[1]]:
print e
for i in s[e[1]]:
if(i not in s[e[0]]):
s[e[0]].append(i)
s[e[1]] = s[e[0]]
其中涉及到集合的合并和比较。