Union-find (disjoint sets)

Beams get bolted together one connection at a time. After each new connection you want to know: are beam 3 and beam 8 now part of the same assembly? How many separate assemblies are there? Re-running BFS after every connection would be slow. Union-find (also called a disjoint-set union, DSU) answers these questions in practically constant time while the groups keep merging.

Two operations

• Find(x): which group is x in? Returns a representative item (the group’s “root”). Two items are in the same group if and only if they have the same root.
• Union(x, y): merge the groups of x and y into one.

Each group is stored as a tree, but all you keep is one array: parent[i] is the item above i, and a root is its own parent. Find walks up the parents to the root. Union finds both roots and makes one the parent of the other: one array write.

Two tricks that make it fast

Done naively, unions can build a long chain, and Find becomes O(n). Two simple improvements fix that:

• Union by rank (or size): attach the shorter tree under the taller one, never the other way round. Trees then stay at most log₂ n tall.
• Path compression: after Find walks up to the root, point every item on that path directly at the root. The next Find for any of them is one step.

With both, a sequence of m operations takes O(m · α(n)), where α is the inverse Ackermann function. It grows so slowly that α(n) ≤ 4 for any n you could ever store. In practice: constant time.

1var beams = new DisjointSet(10);2int[][] bolts = { new[] { 1, 2 }, new[] { 3, 4 }, new[] { 2, 4 }, new[] { 5, 6 }, new[] { 7, 8 }, new[] { 6, 8 } };3foreach (var b in bolts) beams.Union(b[0], b[1]);4 5Console.WriteLine($"Assemblies: {beams.Count}");6Console.WriteLine($"1 and 3 connected? {beams.Connected(1, 3)}");7Console.WriteLine($"1 and 5 connected? {beams.Connected(1, 5)}");8Console.WriteLine($"Union(4, 4) merged anything? {beams.Union(4, 4)}");9 10class DisjointSet11{12    private readonly int[] _parent, _rank;13    public int Count { get; private set; }          // number of separate groups14 15    public DisjointSet(int n)16    {17        _parent = new int[n];18        _rank = new int[n];19        for (int i = 0; i < n; i++) _parent[i] = i;  // everyone starts alone20        Count = n;21    }22 23    public int Find(int x)24    {25        if (_parent[x] != x)26            _parent[x] = Find(_parent[x]);           // path compression27        return _parent[x];28    }29 30    public bool Union(int a, int b)31    {32        int ra = Find(a), rb = Find(b);33        if (ra == rb) return false;                  // already in the same group34        if (_rank[ra] < _rank[rb]) (ra, rb) = (rb, ra);35        _parent[rb] = ra;                            // shorter tree under the taller one36        if (_rank[ra] == _rank[rb]) _rank[ra]++;37        Count--;38        return true;39    }40 41    public bool Connected(int a, int b) => Find(a) == Find(b);42}

Assemblies: 4
1 and 3 connected? True
1 and 5 connected? False
Union(4, 4) merged anything? False

Ten beams, six bolts, four assemblies: {0}, {1, 2, 3, 4}, {5, 6, 7, 8} and {9}. Union returning false is a useful signal on its own: it means the two items were already connected, so this new connection closes a loop.

Where union-find is used

• Kruskal’s MST: “are the ends of this edge already connected?”
• Cycle detection in undirected graphs as edges arrive.
• Dynamic connectivity: network links coming up one by one, “are these two computers connected yet?”
• Grouping equal things: merging duplicate customer records that share an email or phone number, or labelling connected regions in an image.

1int[][] links = { new[] { 1, 2 }, new[] { 2, 3 }, new[] { 3, 4 }, new[] { 1, 4 }, new[] { 1, 5 } };2var loop = FirstLoop(5, links);3Console.WriteLine(loop is null ? "no loop" : $"({loop[0]}, {loop[1]})");4 5static int[]? FirstLoop(int n, int[][] links)6{7    var ds = new DisjointSet(n + 1);8    foreach (var link in links)9        if (!ds.Union(link[0], link[1])) return link;   // already connected: this closes a loop10    return null;11}12 13class DisjointSet14{15    private readonly int[] _parent, _rank;16    public DisjointSet(int n)17    {18        _parent = new int[n];19        _rank = new int[n];20        for (int i = 0; i < n; i++) _parent[i] = i;21    }22    public int Find(int x) => _parent[x] == x ? x : _parent[x] = Find(_parent[x]);23    public bool Union(int a, int b)24    {25        int ra = Find(a), rb = Find(b);26        if (ra == rb) return false;27        if (_rank[ra] < _rank[rb]) (ra, rb) = (rb, ra);28        _parent[rb] = ra;29        if (_rank[ra] == _rank[rb]) _rank[ra]++;30        return true;31    }32}

(1, 4)