AntInLoop

Union-Find (Disjoint Set Union / DSU)

Union-Find (Disjoint Set Union) maintains a partition of elements into disjoint sets with near-constant O(alpha(n)) find and union operations using path compression and union by rank/size.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Union-Find (Disjoint Set Union / DSU)

Union-Find (also called Disjoint Set Union / DSU) tracks a collection of disjoint sets and supports two operations in $O(\alpha(n))$ amortized time (where $\alpha$ is the inverse Ackermann function, $\alpha(n) \le 4$ for every $n$ smaller than the number of atoms in the universe!):

  • find(x): Returns the canonical representative (root) of x's set.
  • unite(a, b): Merges the sets containing a and b.

Combining Path Compression (flattening parent pointers during find) with Union by Rank / Size (attaching the smaller tree under the larger root) gives near-$O(1)$ speed in ~12 lines of code!

At a Glance

| Operation | Time Complexity |

| :--- | :---: |

| find(x) | $O(\alpha(n)) \approx O(1)$ amortized |

| unite(a, b) | $O(\alpha(n)) \approx O(1)$ amortized |

| connected(a, b) | $O(\alpha(n)) \approx O(1)$ amortized |

| Auxiliary Space | $O(n)$ |

---

Practice Problems

Easy

1. Reusable DSU Template (Path Compression + Union by Size)

Implement a clean DSU tracking component count and component sizes in $O(\alpha(n))$ per op.

Approach: Maintain parent[] and sz[]; flatten paths in find(x) and merge smaller into larger in unite(a, b).

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

struct DSU {
    std::vector<int> p, sz;
    int components;

    explicit DSU(int n) : p(n), sz(n, 1), components(n) {
        std::iota(p.begin(), p.end(), 0);
    }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) std::swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        --components;
        return true;
    }
    int sizeOf(int x) { return sz[find(x)]; }
};

int main() {
    DSU dsu(5);
    dsu.unite(0, 1); dsu.unite(1, 2); dsu.unite(3, 4);
    std::cout << "Components: " << dsu.components << " | size(0)=" << dsu.sizeOf(0) << "\n";
    return 0;
}

</details>

---

Intermediate

2. Redundant Connection (Find Cycle-Forming Edge, LeetCode 684)

Given an undirected graph formed by adding one extra edge to an $n$-node tree (1..n), return the edge that creates a cycle.

Approach: Process edges one by one; the first edge (u, v) where !dsu.unite(u, v) (find(u) == find(v)) is the redundant edge! Time: $O(n \alpha(n))$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

std::pair<int, int> findRedundantEdge(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<int> p(n + 1);
    std::iota(p.begin(), p.end(), 0);
    auto find = [&](auto& self, int x) -> int { return p[x] == x ? x : p[x] = self(self, p[x]); };

    for (const auto& [u, v] : edges) {
        int ru = find(find, u), rv = find(find, v);
        if (ru == rv) return {u, v};
        p[ru] = rv;
    }
    return {-1, -1};
}

int main() {
    auto [u, v] = findRedundantEdge(3, {{1, 2}, {1, 3}, {2, 3}});
    std::cout << u << "-" << v << "\n"; // 2-3
    return 0;
}

</details>

---

Related Structures & Algorithms