In my

previous post I implemented Prim’s algorithm with pairing heap. Now, here’s another way to find the minimum spanning tree, using Kruskal’s algorithm (

Wikipedia) with quick union. If you compare the code between posts, this is a whole lot simpler.

**The gist:**

- For each edge by weight ascending
- If nodes are in same component, forget/skip
- Else take edge and merge the two components

Here’s my implementation used in the solving of SPOJ 368. Cobbled Streets CSTREET, in git and below:

Continue reading →