C++UCS301
Graphs & ApplicationsC++17

Disjoint Set Union

DSU maintains a changing partition of elements and answers whether two elements belong to the same component.

What to understand

  • Parent forest
  • Path compression
  • Union by size or rank
  • Connectivity applications

Remember this

  1. 1Optimised operations are almost constant
  2. 2Find returns a representative
  3. 3Union only different representatives

Detailed notes

Disjoint Set Union represents each component as a parent tree whose root is the component representative. find follows parent links; union connects two roots when their components differ.

Path compression rewrites visited nodes to point near the root, and union by size or rank attaches the smaller tree beneath the larger. Together they give amortised O(α(n)), effectively constant for practical sizes.

How it works

  1. 1Initialise each element as its own parent.
  2. 2Find and compress the representative path.
  3. 3Compare representatives before union.
  4. 4Attach the smaller-rank tree and update metadata.

Worked trace

Union by size with compression

Components {0,1,2} and {3,4}
  1. 1find(2) returns representative 0.
  2. 2find(4) returns representative 3.
  3. 3The first tree is larger, so parent[3] becomes 0.
  4. 4A later find(4) compresses 4 directly toward representative 0.
Result: One component {0,1,2,3,4} with shallow parent paths

Where it is used

  • Kruskal's cycle detection
  • Dynamic connectivity and component counting
  • Image segmentation and offline equivalence processing

Common mistakes

  • Unioning raw elements instead of their roots
  • Mixing rank and size update rules
  • Expecting DSU to support arbitrary component splits

Complexity analysis

OperationBestAverageWorstExtra space
find / unionO(α(n))O(α(n))O(α(n))O(n)

C++ implementation

C++17 reference
main.cpp

Union-Find with both optimisations

Path compression flattens finds; union by size prevents tall trees from forming.

class DSU {
    vector<int> parent, size;
public:
    explicit DSU(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int value) {
        if (parent[value] != value) parent[value] = find(parent[value]);
        return parent[value];
    }
    bool unite(int first, int second) {
        first = find(first); second = find(second);
        if (first == second) return false;
        if (size[first] < size[second]) swap(first, second);
        parent[second] = first;
        size[first] += size[second];
        return true;
    }
};
19 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.