Introduction

What is Union Find ?

Union Find is a data structure that keeps track of elements which are split into one or more disjoint sets. Its has two primary operations: find and union.

Where it is Used ?

1. Kruskal's minimum spanning tree algorithm
2. Grid percolation
3. Network connectivity
4. Least common ancestor in trees
5. Image processing
6. Detecting cycles in undirected graphs
7. Connected components in dynamic graphs

Complexity

a(n) — Amortized constant time (basically near to constant time)

Creating a Union Find

To begin using Union Find, first construct a bijection (a mapping) between your objects and the integers in the range $[0,n)$.

NOTE: This step is not necessary in general, but it will allow us to construct an array-based union find.

Find Operation

To find which component a particular element belongs to find the root of that component by following the parent nodes until a self loop is reached (a node who's parent is itself)

Union Operation

To unify two elements find which are the root nodes of each component and if the root nodes are different make one of the root nodes be the parent of the other.

Path Compression

Path compression is an optimization in Union-Find (DSU) that makes future find() operations much faster.

class DSU { // Disjoint Set Union
public:
    vector<int> parent, sz;

    // Number of connected components currently present.
    // Initially = n, decreases after every successful union.
    int components;

    DSU(int n) {
        parent.resize(n);
        sz.assign(n, 1);

        // Initially, every node is its own parent.
        iota(parent.begin(), parent.end(), 0);

        // Initially every node is an independent component.
        components = n;
    }

    int find(int x) {
        // Find the root and compress the path.
        if (parent[x] == x)
            return x;

        return parent[x] = find(parent[x]);   // Path compression
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);

        // Already in the same component.
        if (a == b)
            return false;

        // Attach the smaller tree to the larger tree.
        if (sz[a] < sz[b])
            swap(a, b);   // Union by size

        parent[b] = a;
        sz[a] += sz[b];

        // Two components merged into one.
        components--;

        return true;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }

    // Returns the size of the component containing x.
    int componentSize(int x) {
        return sz[find(x)];
    }

    // Returns the current number of connected components.
    int getComponents() {
        return components;
    }
};

Usage

DSU dsu(n);

// Merge components
dsu.unite(0, 1);
dsu.unite(1, 2);

// Check if two nodes belong to the same component
if (dsu.same(0, 2)) {
    cout << "Connected\n";
}

// Find the representative (root) of a node
cout << dsu.find(2) << "\n";

// Size of the component containing node 0
cout << dsu.componentSize(0) << "\n";

// Number of connected components currently present
cout << dsu.getComponents() << "\n";