Skip to content

Instantly share code, notes, and snippets.

@m00nlight
Created February 14, 2015 03:18
Show Gist options
  • Save m00nlight/d19f63005dc4f69445ee to your computer and use it in GitHub Desktop.
Save m00nlight/d19f63005dc4f69445ee to your computer and use it in GitHub Desktop.
Python kruskal algorithm for minimum spanning tree
import sys
from heapq import heappush, heappop
class UFSet:
def __init__(self, n):
self.fa = [i for i in range(n)]
def find(self, v):
if v != self.fa[v]:
self.fa[v] = self.find(self.fa[v])
return self.fa[v]
def union(self, a, b):
pa = self.find(a)
pb = self.find(b)
self.fa[pa] = pb
def kruscal(Edges, V):
ufset = UFSet(V)
ret = 0
for w, a, b in Edges:
pa, pb = ufset.find(a), ufset.find(b)
if pa == pb:
continue
else:
ret += w
ufset.union(pa, pb)
return ret
if __name__ == '__main__':
line = sys.stdin.readline()
V, E = line.split()
V, E = int(V), int(E)
Es = []
for i in range(E):
line = sys.stdin.readline()
a, b, w = line.split()
a, b, w = int(a), int(b), int(w)
Es.append((w, a, b))
Es.sort()
sys.stdout.write(str(kruscal(Es, V)) + '\n')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment