Chapter 19 of 30

Disjoint Set Union (DSU)

Master the Disjoint Set Union data structure with path compression and union by rank for efficient connectivity queries.

The Problem DSU SolvesNaive ImplementationOptimization 1: Path CompressionOptimization 2: Union by Rank/SizeComponent Queries

Disjoint Set Union (DSU)

DSU (also called Union-Find) maintains a collection of disjoint sets and efficiently answers: "Are these two elements in the same set?" and "Merge these two sets."

The Problem DSU Solves

Given a graph, repeatedly:

Add an edge (merge two components)
Query whether two nodes are in the same component

Without DSU, each operation takes O(n). With DSU, both operations are nearly O(1) — O(α(n)) where α is the inverse Ackermann function (practically ≤ 4 for any realistic input).

Naive Implementation

hljs cpp

vector<int> parent;

void makeSet(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++) parent[i] = i;
}

int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    parent[rx] = ry;
}

Problem: chains can form, making find O(n) in the worst case.

Optimization 1: Path Compression

When you find the root of x, make every node on the path point directly to the root:

hljs cpp

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // path compression
    }
    return parent[x];
}

After path compression, every node on the path points to the root. Future find calls are O(1).

Optimization 2: Union by Rank/Size

Always attach the smaller tree under the larger tree:

hljs cpp

vector<int> parent, rank;

void makeSet(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 rx = find(x), ry = find(y);
    if (rx == ry) return;  // already in the same set
    if (rank[rx] < rank[ry]) swap(rx, ry);
    parent[ry] = rx;
    if (rank[rx] == rank[ry]) rank[rx]++;
}

Union by Size (Alternative)

hljs cpp

vector<int> parent, size;

void makeSet(int n) {
    parent.resize(n);
    size.resize(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (size[rx] < size[ry]) swap(rx, ry);
    parent[ry] = rx;
    size[rx] += size[ry];
}

Component Queries

Check Connectivity

hljs cpp

bool connected(int x, int y) {
    return find(x) == find(y);
}

Count Components

hljs cpp

int countComponents(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (find(i) == i) count++;
    }
    return count;
}

Find Component Size

hljs cpp

int componentSize(int x) {
    return size[find(x)];  // if using union by size
}

Applications

Kruskal's MST

hljs cpp

// Sort edges by weight
sort(edges.begin(), edges.end(), [](const auto &a, const auto &b) {
    return a.w < b.w;
});

DSU dsu(n);
long long mstWeight = 0;
for (auto &[u, v, w] : edges) {
    if (dsu.find(u) != dsu.find(v)) {
        dsu.unite(u, v);
        mstWeight += w;
    }
}

Detect Cycle in Undirected Graph

hljs cpp

// If both endpoints are already connected, adding this edge creates a cycle
for (auto &[u, v] : edges) {
    if (dsu.find(u) == dsu.find(v)) {
        // cycle detected
    } else {
        dsu.unite(u, v);
    }
}

Number of Connected Components After Removing Edges

Process removals in reverse (union them back) to get the count after each removal.

Summary

DSU: O(α(n)) per operation (practically constant)
Path compression + union by rank = O(α(n)) amortized
Use for: connectivity queries, cycle detection, Kruskal's MST
find(x) returns the representative of x's set
unite(x, y) merges the sets containing x and y

Ch 18: Stacks, Queues & Monotonicity Ch 20: Coordinate Compression, Fenwick Tree & Segment Tree

Prefer reading offline? Download the full book as a PDF.

Download Free Book

Chapter 19 of 30

Disjoint Set Union (DSU)

Master the Disjoint Set Union data structure with path compression and union by rank for efficient connectivity queries.

The Problem DSU SolvesNaive ImplementationOptimization 1: Path CompressionOptimization 2: Union by Rank/SizeComponent Queries

Disjoint Set Union (DSU)

DSU (also called Union-Find) maintains a collection of disjoint sets and efficiently answers: "Are these two elements in the same set?" and "Merge these two sets."

The Problem DSU Solves

Given a graph, repeatedly:

Add an edge (merge two components)
Query whether two nodes are in the same component

Without DSU, each operation takes O(n). With DSU, both operations are nearly O(1) — O(α(n)) where α is the inverse Ackermann function (practically ≤ 4 for any realistic input).

Naive Implementation

hljs cpp

vector<int> parent;

void makeSet(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++) parent[i] = i;
}

int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    parent[rx] = ry;
}

Problem: chains can form, making find O(n) in the worst case.

Optimization 1: Path Compression

When you find the root of x, make every node on the path point directly to the root:

hljs cpp

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // path compression
    }
    return parent[x];
}

After path compression, every node on the path points to the root. Future find calls are O(1).

Optimization 2: Union by Rank/Size

Always attach the smaller tree under the larger tree:

hljs cpp

vector<int> parent, rank;

void makeSet(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 rx = find(x), ry = find(y);
    if (rx == ry) return;  // already in the same set
    if (rank[rx] < rank[ry]) swap(rx, ry);
    parent[ry] = rx;
    if (rank[rx] == rank[ry]) rank[rx]++;
}

Union by Size (Alternative)

hljs cpp

vector<int> parent, size;

void makeSet(int n) {
    parent.resize(n);
    size.resize(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (size[rx] < size[ry]) swap(rx, ry);
    parent[ry] = rx;
    size[rx] += size[ry];
}

Component Queries

Check Connectivity

hljs cpp

bool connected(int x, int y) {
    return find(x) == find(y);
}

Count Components

hljs cpp

int countComponents(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (find(i) == i) count++;
    }
    return count;
}

Find Component Size

hljs cpp

int componentSize(int x) {
    return size[find(x)];  // if using union by size
}

Applications

Kruskal's MST

hljs cpp

// Sort edges by weight
sort(edges.begin(), edges.end(), [](const auto &a, const auto &b) {
    return a.w < b.w;
});

DSU dsu(n);
long long mstWeight = 0;
for (auto &[u, v, w] : edges) {
    if (dsu.find(u) != dsu.find(v)) {
        dsu.unite(u, v);
        mstWeight += w;
    }
}

Detect Cycle in Undirected Graph

hljs cpp

// If both endpoints are already connected, adding this edge creates a cycle
for (auto &[u, v] : edges) {
    if (dsu.find(u) == dsu.find(v)) {
        // cycle detected
    } else {
        dsu.unite(u, v);
    }
}

Number of Connected Components After Removing Edges

Process removals in reverse (union them back) to get the count after each removal.

Summary

DSU: O(α(n)) per operation (practically constant)
Path compression + union by rank = O(α(n)) amortized
Use for: connectivity queries, cycle detection, Kruskal's MST
find(x) returns the representative of x's set
unite(x, y) merges the sets containing x and y

Ch 18: Stacks, Queues & Monotonicity Ch 20: Coordinate Compression, Fenwick Tree & Segment Tree

Prefer reading offline? Download the full book as a PDF.

Download Free Book