Minimum spanning tree and Kruskal with DSU

Many problems ask: connect all the items with minimum total cost. Build a network where every site can reach every other site, but use the fewest or cheapest links. This is the minimum spanning tree problem.

A tree is a connected graph with no cycles. A spanning tree of a graph touches every node exactly once through the edges. A minimum spanning tree has the smallest total edge weight among all spanning trees.

Kruskal's algorithm builds an MST by greedily adding the cheapest edge that does not create a cycle. It works because of a property called the cut property: if you partition the nodes into two groups, the cheapest edge crossing the partition is safe to include in any MST.

The challenge is checking whether adding an edge creates a cycle. You need to know which nodes are already connected through the edges you have chosen so far. A disjoint-set union (DSU), also called union-find, maintains this information efficiently.

Disjoint-set union

A DSU stores a collection of disjoint sets. Each element belongs to exactly one set. Two operations are central: find(x) returns the representative of the set containing x, and union(x, y) merges the sets containing x and y.

Two nodes are in the same connected component if find(x) == find(y). If they are not, you can add an edge between them without creating a cycle.

The simplest implementation uses a parent pointer. Each node points to its parent. The root of the tree points to itself. find(x) walks up the parent pointers until it reaches a root.

1def find(parent, x):2    if parent[x] != x:3        parent[x] = find(parent, parent[x])4    return parent[x]5
6
7def union(parent, x, y):8    root_x = find(parent, x)9    root_y = find(parent, y)10    if root_x != root_y:11        parent[root_y] = root_x

find(x) uses path compression: after finding the root, it makes every node on the path point directly to the root. This keeps future find calls fast.

union(x, y) attaches one root to the other. To avoid creating very deep trees, union by rank attaches the root of the smaller tree to the larger one. With both optimizations, find and union take nearly constant time.

Kruskal's algorithm

1import sys2
3
4def find(parent, x):5    if parent[x] != x:6        parent[x] = find(parent, parent[x])7    return parent[x]8
9
10def union(parent, rank, x, y):11    root_x = find(parent, x)12    root_y = find(parent, y)13
14    if root_x == root_y:15        return False16
17    if rank[root_x] < rank[root_y]:18        parent[root_x] = root_y19    elif rank[root_x] > rank[root_y]:20        parent[root_y] = root_x21    else:22        parent[root_y] = root_x23        rank[root_x] += 124
25    return True26
27
28def main() -> None:29    input_data = sys.stdin.read().split()30    if not input_data:31        return32
33    idx = 034    n = int(input_data[idx])35    m = int(input_data[idx + 1])36    idx += 237
38    edges = []39    for _ in range(m):40        u = int(input_data[idx])41        v = int(input_data[idx + 1])42        w = int(input_data[idx + 2])43        idx += 344        edges.append((w, u, v))45
46    edges.sort()47
48    parent = list(range(n))49    rank = [0] * n50    total_weight = 051    edges_used = 052
53    for w, u, v in edges:54        if union(parent, rank, u, v):55            total_weight += w56            edges_used += 157            if edges_used == n - 1:58                break59
60    if edges_used == n - 1:61        sys.stdout.write(str(total_weight) + "\n")62    else:63        sys.stdout.write("-1\n")64
65
66if __name__ == "__main__":67    main()

4 5
0 1 2
1 2 3
0 2 4
2 3 1
1 3 5

6

The algorithm sorts edges by weight and processes them in order. For each edge, check if its endpoints are in different components using find. If they are, add the edge and merge the components. If they are already in the same component, skip the edge because adding it would create a cycle.

The result is a tree connecting all nodes with minimum total weight.

Why Kruskal's algorithm works

The cut property guarantees that Kruskal's greedy choice is safe. Partition the nodes into two groups: those already in the MST so far, and those not yet added. The cheapest edge crossing the partition between these two groups can appear in some MST. If it is not in an MST, you could swap it with the edge of equal or higher cost that the MST uses to cross the partition, creating an MST of equal or lower cost. So greedily adding the cheapest edge never closes off a path to the optimal solution.

The algorithm processes n - 1 edges: enough to connect n nodes into a tree. It rejects any edge that would create a cycle because its endpoints are already connected through earlier choices. This guarantees the result is acyclic and spanning.

The time complexity is O(m log m) for sorting edges, plus $O(m \cdot \alpha(n))$ for DSU operations, where $\alpha$ is the inverse Ackermann function (effectively constant). The total time is dominated by sorting.

A second example: highway network

A country has 6 cities and wants to connect them with highways. The cost is the total length of highways built. The practical distances are: cities 0-1 cost 5, 0-2 cost 8, 0-3 cost 6, 1-2 cost 3, 1-4 cost 7, 2-3 cost 4, 3-4 cost 2, and 3-5 cost 9.

Sort the edges by cost: (3-4, 2), (1-2, 3), (2-3, 4), (0-1, 5), (0-3, 6), (1-4, 7), (0-2, 8), (3-5, 9).

Process each edge in order. Initially, each city is its own component. Edge 3-4 costs 2: add it, merging 3 and 4. Edge 1-2 costs 3: add it, merging 1 and 2. Edge 2-3 costs 4: add it, merging 2 and 4 into 4. Edge 0-1 costs 5: add it, merging 0 and 4. Edge 0-3 costs 6: both endpoints are already in 4, so skip it. Edge 1-4 costs 7: skip (both in same component). Edge 0-2 costs 8: skip. Edge 3-5 costs 9: add it, merging 4 and 5. Total cost: 2 + 3 + 4 + 5 + 9 = 23. You have added 5 edges connecting 6 cities, so all are reachable.

Common mistakes

One mistake is to forget to update the parent correctly in union. If you set parent[root_x] = root_y, then later calls to find(x) will fail because the root has changed. You must always retrieve both roots first, check if they differ, and only then update the parent. Otherwise, find descends through an invalid path and returns an incorrect root.

Another mistake is to skip path compression in find. Without it, find becomes slow on deep trees. Consider a chain of 1,000 nodes where node i points to node i+1, and the last node points to itself. The first find call walks the entire chain, taking 1,000 steps. With path compression, that same call makes every node point directly to the root, so future calls take one step each. Even with union by rank, skipping compression allows deep trees to form in the worst case and degrades union-find toward O(n) per operation instead of nearly constant.

A third mistake is to check connectivity incorrectly. The condition if find(x) != find(y) means x and y are not yet in the same component, so it is safe to add an edge. If you check if x == y, you compare node ids instead of component representatives. This misses many edges that should be added because their endpoints are in different components.

Recap

A minimum spanning tree connects all nodes with minimum total edge weight and contains no cycles. Kruskal's algorithm builds an MST by sorting edges and greedily adding the cheapest edge that does not create a cycle. A disjoint-set union detects whether two nodes are already connected. With path compression and union by rank, DSU operations take nearly constant time per call, making Kruskal's algorithm efficient on large graphs.