A solution to the minimal spanning tree problem in Java, using a clever data structure.
I sometimes solve problems on UVa Online Judge, as a way of building & practicing my algorithmic skills. UVa 11631 - Dark Roads is the first problem I'll write about. On the surface, it's a very standard Minimal Spanning Tree problem - solvable with either Prim or Kruskal's algorithm.
My first attempt was to solve this with Prim's, and use Java's standard priority queue. Sadly, as it turns out, the Java priority queue implementation does not re-order nodes in the heap when the object's priority changes. So reinserting each node when its priority changed is a horrible loss of efficiency and indeed this approach results in TLE.
Kruskal is the better algorithm to use in this case, as the graph is definitely sparse. The trick with Kruskal is to use a good data structure for performing union over disjoint sets. The following solution uses the data structure described in Cormen et al.1: