Road Reparation - Implementation

Here is the Kruskal implementation:

sort edges by weight
parent = array [0, 1, 2, ..., n-1]
totalCost = 0
edgeCount = 0

for (u, v, w) in edges:
    if find(u) != find(v):
        union(u, v)
        totalCost = totalCost + w
        edgeCount = edgeCount + 1

if edgeCount == n - 1:
    print totalCost
else:
    print "IMPOSSIBLE"

Time: $O(m \log m)$ for sorting. Space: $O(n)$ for Union-Find.