Disjoint Set Union / Union-Find from Scratch (2026)

Disjoint Set Union (DSU), also known as Union-Find, is a data structure that tracks a set of elements partitioned into disjoint (non-overlapping) subsets. It supports two operations efficiently: find (determine which subset an element belongs to) and union (merge two subsets). It is fundamental in graph algorithms like Kruskal's MST, cycle detection, and connected components.

With path compression and union by rank (or size), the amortized time complexity per operation approaches O(α(n)), where α is the inverse Ackermann function — practically constant for all reasonable input sizes.

class DSU {
  vector parent, rank;
public:
  DSU(int n) {
    parent.resize(n);
    rank.resize(n, 0);
    for (int i = 0; i < n; i++) parent[i] = i;
  }
  int find(int x) {
    if (parent[x] != x)
      parent[x] = find(parent[x]);
    return parent[x];
  }
  void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (rank[px] < rank[py]) parent[px] = py;
    else if (rank[px] > rank[py]) parent[py] = px;
    else { parent[py] = px; rank[px]++; }
  }
};

# Python: DSU with cycle detection
def has_cycle(n, edges):
    parent = list(range(n))
    rank = [0] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return False
        if rank[rx] < rank[ry]: parent[rx] = ry
        elif rank[rx] > rank[ry]: parent[ry] = rx
        else: parent[ry] = rx; rank[rx] += 1
        return True
    for u, v in edges:
        if not union(u, v): return True
    return False

Originally published on Ayodhyyya. Last updated June 1, 2026.