Disjoint Set Union: Union by Rank, Size and Path Compression

89.1k
1

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N. Initially, every node belongs to a separate set.

Support the following operations:

DisjointSet(int n): Initialize a disjoint set containing n nodes.

unionByRank(int u, int v): Merge the sets containing u and v using the rank heuristic.

unionBySize(int u, int v): Merge the sets containing u and v using the size heuristic.

find(int u, int v): Return true when u and v belong to the same set; otherwise, return false.

The implementation also provides componentSizeOf(node) for retrieving the number of nodes in the set containing node.

Example 1

Input: N = 5, operations = [unionByRank(1,2), unionByRank(2,3), find(1,3), find(1,5)]

Output: [true, false]

Explanation: Rank-based merges place nodes 1, 2, and 3 in one set. Node 5 remains in a separate set.

Example 2

Input: N = 5, operations = [unionBySize(1,2), unionBySize(4,5), unionBySize(2,4), find(1,5), componentSizeOf(1)]

Output: [true, 4]

Explanation: Size-based merges create one set containing nodes 1, 2, 4, and 5.

Approach 1

A parent array represents every set as a rooted tree. Root nodes store the root index in the parent array. Path compression rewrites parent links directly to the representative during findParent, shortening future representative searches.

Rank approximates tree height. unionByRank attaches the lower-rank root below the higher-rank root. Equal ranks allow either root to become the representative, followed by one rank increment.

Algorithm

  • Initialize parent[node]=node, rankValue[node]=0, and componentSize[node]=1 for every node.

  • Run findParent(node) until reaching a root satisfying parent[node]=node.

  • Assign the representative during recursive return, compressing every visited parent link.

  • Run findParent for both nodes before unionByRank and stop after matching representatives.

  • Attach the lower-rank root below the higher-rank root and update the surviving component size.

  • Attach either root for equal ranks, increment the surviving rank, and update the surviving component size.

  • Run find(u, v) through representative comparison.

Dry Run

union by rank

union by rank

Solution

#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
private:
vector<int> parent;
vector<int> rankValue;
public:
// Initializes one independent set for every node.
DisjointSet(int n) {
parent.resize(n + 1);
rankValue.assign(n + 1, 0);
// Make every node its own parent.
for (int node = 1; node <= n; node++) {
parent[node] = node;
}
}
// Returns the representative using path compression.
int findParent(int node) {
// Base case: node is its own representative.
if (parent[node] == node) {
return node;
}
// Compress the path while finding the representative.
parent[node] = findParent(parent[node]);
return parent[node];
}
// Merges two sets using rank balancing.
void unionByRank(int u, int v) {
int rootU = findParent(u);
int rootV = findParent(v);
// Same representative means both nodes are already connected.
if (rootU == rootV) {
return;
}
// Keep the higher-rank root as the parent.
if (rankValue[rootU] < rankValue[rootV]) {
swap(rootU, rootV);
}
// Attach the lower-rank root to the higher-rank root.
parent[rootV] = rootU;
// Increase rank only when both ranks are equal.
if (rankValue[rootU] == rankValue[rootV]) {
rankValue[rootU]++;
}
}
// Checks whether two nodes share one set.
bool find(int u, int v) {
return findParent(u) == findParent(v);
}
};
// Driver code.
int main() {
DisjointSet dsu(5);
dsu.unionByRank(1, 2);
dsu.unionByRank(2, 3);
cout << boolalpha << dsu.find(1, 3) << "\n";
cout << boolalpha << dsu.find(1, 5) << "\n";
return 0;
}

Complexity Analysis

Time Complexity: O(α(N)) amortized per findParent, unionByRank, or find operation after O(N) initialization, where α is the inverse Ackermann function.

Space Complexity: O(N), where the parent, rank, and component-size arrays store one entry for every node.

Approach 2

The parent forest and path-compressed findParent operation remain unchanged. A component-size array stores the number of nodes belonging to each current representative.

unionBySize attaches the smaller set below the larger set. The surviving representative receives the combined component size, allowing componentSizeOf(node) to return set cardinality directly.

Algorithm

  • Initialize parent[node]=node, rankValue[node]=0, and componentSize[node]=1 for every node.

  • Run findParent(node) until reaching a root and compress the complete parent path during return.

  • Run findParent for both nodes before unionBySize and stop after matching representatives.

  • Compare both component sizes and swap representatives after locating a larger second component.

  • Attach the smaller representative below the larger representative.

  • Add the absorbed component size to the surviving representative and preserve a valid rank upper bound.

  • Run find(u, v) through representative comparison and run componentSizeOf(node) through the representative size.

Dry Run

union by size

union by size

Solution

#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
private:
vector<int> parent;
vector<int> componentSize;
public:
// Initializes one independent set for every node.
DisjointSet(int n) {
parent.resize(n + 1);
componentSize.assign(n + 1, 1);
// Make every node its own parent.
for (int node = 1; node <= n; node++) {
parent[node] = node;
}
}
// Returns the representative using path compression.
int findParent(int node) {
// Base case: node is its own representative.
if (parent[node] == node) {
return node;
}
// Compress the path while finding the representative.
parent[node] = findParent(parent[node]);
return parent[node];
}
// Merges two sets using component-size balancing.
void unionBySize(int u, int v) {
int rootU = findParent(u);
int rootV = findParent(v);
// Same representative means both nodes are already connected.
if (rootU == rootV) {
return;
}
// Keep the larger component as the main parent.
if (componentSize[rootU] < componentSize[rootV]) {
swap(rootU, rootV);
}
// Attach the smaller component to the larger component.
parent[rootV] = rootU;
// Update the size of the merged component.
componentSize[rootU] += componentSize[rootV];
}
// Checks whether two nodes share one set.
bool find(int u, int v) {
return findParent(u) == findParent(v);
}
// Returns the number of nodes in one set.
int componentSizeOf(int node) {
return componentSize[findParent(node)];
}
};
// Driver code.
int main() {
DisjointSet dsu(5);
dsu.unionBySize(1, 2);
dsu.unionBySize(4, 5);
dsu.unionBySize(2, 4);
cout << boolalpha << dsu.find(1, 5) << "\n";
cout << dsu.componentSizeOf(1) << "\n";
return 0;
}

Complexity Analysis

Time Complexity: O(α(N)) amortized per findParent, unionBySize, find, or componentSizeOf operation after O(N) initialization, where α is the inverse Ackermann function.

Space Complexity: O(N), where the parent, rank, and component-size arrays store one entry for every node.

Interview follow-up Questions

Every visited node receives a direct link to the representative, so later searches traverse fewer parent links.

Graph

Read Similar Blogs

Graph

Find the City with the Smallest Number of Neighbors at a Threshold Distance

Given N cities numbered from 0 to N-1 , an array of bidirectional weighted roads [first, second, weight] , and a positive distanceThreshold , count the other cities reachable from every city with s...

105.7k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge appears as [u, v,...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Comments0