Disjoint Set Union (Union-Find)

Concept

DSU keeps a parent pointer for each element. find(x) follows parents to the root (the group's representative); union(a, b) links two roots.

Two optimisations make it almost O(1): path compression (point nodes directly at the root during find) and union by rank/size (attach the smaller tree under the larger).

Used for dynamic connectivity, cycle detection in undirected graphs, and Kruskal's minimum spanning tree.

Complexity

Code (Python)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

def kruskal(n, edges):           # edges: (w, u, v)
    dsu, total = DSU(n), 0
    for w, u, v in sorted(edges):
        if dsu.union(u, v):
            total += w
    return total

Remember

• union returning False = edge creates a cycle.
• Count components = number of successful unions subtracted from n.
• Kruskal = sort edges + DSU.