{"id":4587,"date":"2024-10-21T11:03:01","date_gmt":"2024-10-21T11:03:01","guid":{"rendered":"https:\/\/algocademy.com\/blog\/union-find-disjoint-set-a-comprehensive-guide-for-efficient-data-structure-operations\/"},"modified":"2026-10-15T10:34:50","modified_gmt":"2026-10-15T10:34:50","slug":"union-find-disjoint-set-a-comprehensive-guide-for-efficient-data-structure-operations","status":"publish","type":"post","link":"https:\/\/algocademy.com\/blog\/union-find-disjoint-set-a-comprehensive-guide-for-efficient-data-structure-operations\/","title":{"rendered":"Union-Find (Disjoint Set): How It Works, With Python Code"},"content":{"rendered":"<p>Union-Find, also called a disjoint set union (DSU), keeps track of which elements belong to the same group and lets you merge two groups. It supports two operations, <code>find(x)<\/code> (which group is x in?) and <code>union(a, b)<\/code> (merge the groups of a and b), and with two small optimizations each operation takes close to constant time. It is the standard tool for questions like &#8220;are these two nodes connected?&#8221;, &#8220;how many components are there?&#8221; and &#8220;does adding this edge create a cycle?&#8221;.<\/p>\n<h2>How it works<\/h2>\n<p>Each group is a tree stored in an array. <code>parent[i]<\/code> is the parent of element i, and the root of a tree (an element that is its own parent) is the group&#8217;s representative. Two elements are in the same group if and only if <code>find<\/code> returns the same root for both.<\/p>\n<ul>\n<li><code>find(x)<\/code> walks up parent links until it reaches the root.<\/li>\n<li><code>union(a, b)<\/code> finds both roots and, if they differ, makes one root the child of the other.<\/li>\n<\/ul>\n<p>Without any optimization, unioning elements in a bad order creates a long chain, and each <code>find<\/code> becomes O(n). Two ideas fix that.<\/p>\n<h3>Path compression<\/h3>\n<p>While walking up to the root in <code>find<\/code>, point each visited node closer to the root. The next <code>find<\/code> on those nodes is shorter. The version below uses &#8220;path halving&#8221;, which does this in a simple loop and avoids the recursion-depth problem of the textbook recursive version.<\/p>\n<h3>Union by size (or rank)<\/h3>\n<p>When merging, attach the smaller tree under the root of the larger one. This keeps trees shallow. Rank (an upper bound on tree height) works the same way; size is easier to understand and lets you ask for the size of a group for free.<\/p>\n<p>With both optimizations, a sequence of m operations on n elements takes O(m\u00b7\u03b1(n)) time, where \u03b1 is the inverse Ackermann function. It grows so slowly that it is at most 4 or 5 for any input that fits in a computer, so treat it as constant.<\/p>\n<h2>Implementation<\/h2>\n<pre><code class=\"language-python\">class UnionFind:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.size = [1] * n\n        self.count = n          # number of separate groups\n\n    def find(self, x):\n        while self.parent[x] != x:\n            self.parent[x] = self.parent[self.parent[x]]   # path halving\n            x = self.parent[x]\n        return x\n\n    def union(self, a, b):\n        ra, rb = self.find(a), self.find(b)\n        if ra == rb:\n            return False        # already in the same group\n        if self.size[ra] &lt; self.size[rb]:\n            ra, rb = rb, ra\n        self.parent[rb] = ra    # attach smaller tree under larger\n        self.size[ra] += self.size[rb]\n        self.count -= 1\n        return True\n\n    def connected(self, a, b):\n        return self.find(a) == self.find(b)\n\nuf = UnionFind(6)\nuf.union(0, 1); uf.union(2, 3); uf.union(1, 2)\nprint(uf.connected(0, 3))   # True\nprint(uf.connected(0, 4))   # False\nprint(uf.count)             # 3  -> groups {0,1,2,3}, {4}, {5}\nprint(uf.union(0, 3))       # False (already connected)\n<\/code><\/pre>\n<p>Returning <code>True<\/code> or <code>False<\/code> from <code>union<\/code> is a small design choice that pays off: many problems need to know whether the union actually merged two different groups.<\/p>\n<p>Union-Find only grows groups. It cannot split a group or remove an element efficiently. If a problem needs deletions, think about processing the operations in reverse (turning deletions into unions) or a different structure.<\/p>\n<h2>Use case 1: count connected components<\/h2>\n<p>Union every edge, then read <code>count<\/code>. The same pattern solves &#8220;number of provinces&#8221; and &#8220;number of connected components in an undirected graph&#8221;.<\/p>\n<pre><code class=\"language-python\">def count_components(n, edges):\n    uf = UnionFind(n)\n    for a, b in edges:\n        uf.union(a, b)\n    return uf.count\n\nprint(count_components(5, [(0, 1), (1, 2), (3, 4)]))   # 2\n<\/code><\/pre>\n<p>A DFS or BFS gives the same answer in O(n + e). Union-Find is better when edges arrive one at a time and you need the answer after each one (an &#8220;online&#8221; problem), because a traversal would have to start over.<\/p>\n<h2>Use case 2: detect a cycle in an undirected graph<\/h2>\n<p>If an edge connects two nodes that are already in the same group, that edge closes a cycle. This is exactly &#8220;Redundant Connection&#8221;: return the edge that can be removed to leave a tree.<\/p>\n<pre><code class=\"language-python\">def find_redundant_connection(edges):\n    uf = UnionFind(len(edges) + 1)      # nodes are numbered from 1\n    for a, b in edges:\n        if not uf.union(a, b):\n            return [a, b]\n\nprint(find_redundant_connection([(1, 2), (1, 3), (2, 3)]))                  # [2, 3]\nprint(find_redundant_connection([(1, 2), (2, 3), (3, 4), (1, 4), (1, 5)]))  # [1, 4]\n<\/code><\/pre>\n<p>This only works for undirected graphs. For directed graphs, cycle detection needs a DFS with colors or a topological sort.<\/p>\n<h2>Use case 3: Kruskal&#8217;s minimum spanning tree<\/h2>\n<p>Kruskal&#8217;s algorithm sorts the edges by weight and adds each edge unless it would form a cycle. Union-Find answers the &#8220;would it form a cycle&#8221; question in near-constant time, so the sort dominates: O(E log E).<\/p>\n<pre><code class=\"language-python\">def kruskal(n, edges):\n    \"\"\"edges are (weight, a, b)\"\"\"\n    uf = UnionFind(n)\n    mst, total = [], 0\n    for w, a, b in sorted(edges):\n        if uf.union(a, b):\n            mst.append((a, b, w))\n            total += w\n    return total, mst\n\nedges = [(1, 0, 1), (2, 1, 2), (3, 2, 3), (4, 3, 0), (5, 0, 2)]\nprint(kruskal(4, edges))   # (6, [(0, 1, 1), (1, 2, 2), (2, 3, 3)])\n<\/code><\/pre>\n<h2>Use case 4: grids (number of islands)<\/h2>\n<p>A grid is a graph where neighboring land cells are connected. Map cell (r, c) to the index <code>r * C + c<\/code>, union each land cell with its right and lower land neighbors, then count the groups that contain land.<\/p>\n<pre><code class=\"language-python\">def num_islands(grid):\n    R, C = len(grid), len(grid[0])\n    uf = UnionFind(R * C)\n    land = 0\n    for r in range(R):\n        for c in range(C):\n            if grid[r][c] == \"1\":\n                land += 1\n                for dr, dc in ((1, 0), (0, 1)):\n                    nr, nc = r + dr, c + dc\n                    if nr &lt; R and nc &lt; C and grid[nr][nc] == \"1\":\n                        uf.union(r * C + c, nr * C + nc)\n    return uf.count - (R * C - land)   # drop the one-element groups made by water\n\nprint(num_islands([\"11000\", \"11000\", \"00100\", \"00011\"]))   # 3\n<\/code><\/pre>\n<p>For this one-shot problem a DFS is just as good and many people find it easier. Union-Find wins on the follow-up &#8220;Number of Islands II&#8221;, where land cells are added one at a time and you must report the count after each addition.<\/p>\n<h2>Other problems where it fits<\/h2>\n<ul>\n<li><strong>Accounts merge \/ similar-items grouping:<\/strong> union items that share a key (an email, a label), then group by root.<\/li>\n<li><strong>Equations like a == b and a != b:<\/strong> union all the equalities first, then check the inequalities.<\/li>\n<li><strong>Percolation, network connectivity, friend circles:<\/strong> any &#8220;are these connected?&#8221; with incremental connections.<\/li>\n<\/ul>\n<h2>Complexity<\/h2>\n<table>\n<thead>\n<tr>\n<th>Operation<\/th>\n<th>Time (amortized)<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>Build with n elements<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><code>find<\/code><\/td>\n<td>O(\u03b1(n)), effectively constant<\/td>\n<\/tr>\n<tr>\n<td><code>union<\/code><\/td>\n<td>O(\u03b1(n)), effectively constant<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Memory is O(n) for the parent and size arrays.<\/p>\n<h2>Common mistakes<\/h2>\n<ul>\n<li><strong>Calling <code>union<\/code> on the elements instead of on their roots.<\/strong> Set <code>parent[a] = b<\/code> and you break the structure for every other element in a&#8217;s group. Always find the roots first.<\/li>\n<li><strong>Reading <code>parent[x]<\/code> directly<\/strong> to compare groups. It is only the root after you call <code>find(x)<\/code>.<\/li>\n<li><strong>Off-by-one with 1-indexed nodes.<\/strong> Allocate n + 1 elements, as in the redundant connection example.<\/li>\n<li><strong>Using the recursive <code>find<\/code> on a long chain<\/strong> in Python. It can hit the recursion limit before path compression has helped. The iterative loop above does not.<\/li>\n<li><strong>Using it for deletions or directed graphs.<\/strong> Neither is what the structure does.<\/li>\n<\/ul>\n<h2>Practice<\/h2>\n<p>Implement the class from memory, then solve Number of Provinces, Redundant Connection and Number of Islands II. If graph traversal is still shaky, read <a href=\"https:\/\/algocademy.com\/blog\/breadth-first-search-bfs-a-comprehensive-guide-for-algorithmic-problem-solving\/\">breadth-first search<\/a> first, since Union-Find is usually the second tool you reach for on connectivity problems. You can practice the graph side on AlgoCademy with the <a href=\"https:\/\/algocademy.com\/link\/?lang=py&amp;problem=find-if-path-exist-in-a-graph&amp;solution=1\">Find if Path Exists in Graph exercise<\/a>, and see <a href=\"https:\/\/algocademy.com\/blog\/when-to-use-a-visited-set-in-graph-problems-a-comprehensive-guide\/\">when to use a visited set<\/a> for the traversal alternative.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Learn the Union-Find (disjoint set) data structure: find, union, path compression, union by size, and its use in components, cycles and Kruskal&#8217;s MST.<\/p>\n","protected":false},"author":1,"featured_media":4586,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-4587","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4587"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=4587"}],"version-history":[{"count":1,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4587\/revisions"}],"predecessor-version":[{"id":8756,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4587\/revisions\/8756"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/4586"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=4587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=4587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=4587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}