Disjoint Set (Union Find Algorithm)

Example of Disjoint Set

#include <iostream>
#include <vector>

class DisjointSet {
private:
    std::vector<int> parent;
public:
    DisjointSet(int n) : parent(n) {
        for (int i = 0; i < n; ++i)
            parent[i] = i; // Initialize each element as its own set
    }

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

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY)
            parent[rootY] = rootX; // Union by rank
    }
};

int main() {
    DisjointSet ds(5);
    ds.unionSets(0, 1);
    ds.unionSets(2, 3);
    ds.unionSets(0, 3);
    std::cout << "Parent array after union operations: ";
    for (int i = 0; i < 5; ++i)
        std::cout << ds.find(i) << " ";
    std::cout << std::endl;
    return 0;
}

Output:

Parent array after union operations: 0 0 0 0 4

Explanation:

• Initially, each element is its own set, so the parent array looks like: [0, 1, 2, 3, 4].
• After the union operation ds.unionSets(0, 1), sets containing elements 0 and 1 are merged. The parent array becomes: [0, 0, 2, 3, 4].
• After the union operation ds.unionSets(2, 3), sets containing elements 2 and 3 are merged. The parent array remains: [0, 0, 2, 2, 4].
• After the union operation ds.unionSets(0, 3), sets containing elements 0 and 3 are merged. Since 0 is the representative element of the set, the parent of 3 becomes 0. The parent array becomes: [0, 0, 2, 0, 4].
• The final parent array represents the disjoint sets after all union operations.

Operations on Disjoint Set Data Structures 

Two operations that can be performed on Disjoint sets are- find and union. Let us understand what they are one by one.

Find

The find operation in a disjoint set data structure is used to find the representative element (also known as the root) of the set to which a given element belongs. It utilizes path compression to optimize subsequent find operations by making each element point directly to its root.

Implementation:

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

Union

The union operation in a disjoint set data structure merges two sets by making one of the representative elements the parent of the other. It employs union by rank to maintain the balance of the resulting disjoint sets, ensuring efficient find operations.

Implementation:

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
        parent[rootY] = rootX; // Union by rank
}

These operations are crucial for efficiently managing disjoint sets, facilitating tasks like connectivity queries and cycle detection in graphs.

Naive Implementation

A naive implementation of disjoint set data structure involves directly implementing the basic operations without any optimizations like path compression or union by rank. In this approach, the find operation typically traverses the parent pointers until it reaches the root element, without any optimization for path compression. Similarly, the union operation simply merges two sets without considering their sizes or depths, leading to potentially unbalanced trees.

Naive Find Implementation:

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

Naive Union Implementation:

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}

While this naive approach is straightforward to implement, it may result in inefficient find operations, especially when dealing with large disjoint sets or heavily interconnected data structures. Consequently, it's generally less performant compared to optimized implementations utilizing techniques like path compression and union by rank.

Optimizations

In disjoint set data structures, optimizations are employed to enhance the efficiency of operations such as finding the representative element of a set and merging two sets. These optimizations aim to reduce the time complexity of these operations, making them more suitable for practical applications, especially in scenarios involving large datasets or frequent operations.

There are two ways to improve it

1. Path Compression
2. Union by Rank

Path Compression

Path compression is a method of flattening the tree structure when find_set(x) is used on it.

This optimization is designed for speeding up the find_set(x) operation.

If we call find_set(x) for some vertex x, we actually find the representative p for all vertices that we visit on the path between x and the actual representative p. 

Here the trick is to make the paths for all those nodes shorter, by setting the parent of each visited vertex directly to p. 

Therefore, the resulting tree is much flatter, which speeds up future operations on these elements as well as those that reference them.

Consider the below diagram for better understanding:

The left side shows a tree whereas the right side shows a compressed tree for visited nodes 2,3,5,7.

Implementation

The new implementation of find_set(x) is as follows:

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

Complexity Analysis

Time Complexity: O(log N), where n is the number of nodes.

Space Complexity: O(n), where n is the number of nodes.

Let’s move on to other optimization i.e. union by rank without further ado.

Union by Rank

As we already know when we call find_set(x) and find_set(y) is called it finds the roots that belong to the trees x and y. If the roots of the trees are distinct, the trees are merged by connecting the roots of one to the roots of the other. If this is done carelessly, such as by always making x a child of y, the trees' height can grow as O(n). 

We can improve it by employing union by rank.

There are numerous ways that can be taken into account. Here we will discuss the two most popular and most used:

1. Union by rank based on size
2. Union by rank based on depth

The underlying principle of the optimization is the same in both approaches: we attach the tree with the lower rank to the one with the higher rank.

Union by rank based on size

Earlier, we stored i (in the parent array) for the root element and the parent of i for other elements. However, in this approach, we store the reverse of the tree size (that is, if the tree size is 3, we store –3 in the parent array for the root element). 

Assume that the size of one element set is 1 and store – 1. Other than this there is no change. 

Implementation

void make_set(int v) {
    parent[v] = v;
    size[v] = -1;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (abs(size[a]) < abs(size[b]))
            swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
}

Union by rank based on depths

In contrast with UNION by size, in this method, we store the depths instead of height because path compression will change the trees’ heights over time.

Each element is associated with a rank. Initially, a set has one element and a rank of zero.

Implementation

void make_set(int v) {
    parent[v] = v;
    rank[v] = 0;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            rank[a]++;
    }
}

Note: For the find_set(x) operation there is no change in the implementation. 

Complexity Analysis

Both optimizations are equivalent in terms of time and space complexity.

Time Complexity: O(log N), where n is the number of nodes.

Space Complexity: O(n), where n is the number of nodes.

So in practice, you can use any of them.

Implementation of Disjoint Set

Now that we know the working of the union-find algorithm, we can write the code for it. I’m sure you can write the code yourself, but here’s the solution of all the operations in one place just in case.

// C++ implementation of disjoint set
#include <iostream>
using namespace std;
class DisjointSet {
int *rank, *parent, n;

public:
// Constructor to create and
// initialize sets of n items
DisjointSet(int n)
{
rank = new int[n];
parent = new int[n];
this->n = n;
make_set();
}

// Creates n single item sets
void make_set()
{
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}

// Finds set of given item x
int find_set(int x)
{
// Finds the representative of the set
// that x is an element of
if (parent[x] != x) {

// if x is not the parent of itself
// Then x is not the representative of
// his set,
parent[x] = find_set(parent[x]);

// so we recursively call Find on its parent
// and move i's node directly under the
// representative of this set
}

return parent[x];
}

// Do union of two sets represented
// by x and y.
void Union(int x, int y)
{
// Find current sets of x and y
int xset = find_set(x);
int yset = find_set(y);

// If they are already in same set
if (xset == yset)
return;

// Put smaller ranked item under
// bigger ranked item if ranks are
// different
if (rank[xset] < rank[yset]) {
parent[xset] = yset;
}
else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
}

// If ranks are same, then increment
// rank.
else {
parent[yset] = xset;
rank[xset] = rank[xset] + 1;
}
}
};

int main()
{
DisjointSet obj(5);
obj.Union(0, 2);
obj.Union(4, 2);
obj.Union(3, 1);
if (obj.find_set(4) == obj.find_set(0))
cout << "Yes\n";
else
cout << "No\n";
if (obj.find_set(1) == obj.find_set(0))
cout << "Yes\n";
else
cout << "No\n";

return 0;
}

Must Read Algorithm Types

Applications Of Disjoint Sets

Disjoint set data structures find applications in various fields where efficient management of disjoint sets and connectivity queries is required. Some common applications include:

• Graph Algorithms: Disjoint sets are often used in graph algorithms such as Kruskal's minimum spanning tree algorithm and Borůvka's algorithm for finding the minimum spanning tree. They facilitate efficient connectivity checks and cycle detection in graphs.
• Dynamic Connectivity: Disjoint sets are used to solve dynamic connectivity problems where elements are dynamically added or removed, and connectivity queries need to be answered efficiently. Applications include network connectivity problems and social network analysis.
• Image Processing: Disjoint sets are utilized in image processing tasks like image segmentation, where pixels with similar attributes are grouped together into segments or regions. Disjoint set data structures help efficiently manage these segments and perform operations such as merging or splitting them based on certain criteria.
• Union-Find Applications: Disjoint sets are commonly used in various union-find applications, including data compression algorithms like Huffman coding, which require efficient union and find operations for merging and querying disjoint sets of elements.
• Dynamic Graph Operations: In dynamic graph scenarios where edges and vertices are added or removed dynamically, disjoint set data structures help maintain the connectivity status of the graph efficiently. Applications include network routing algorithms and database management systems.
• Optimization Problems: Disjoint sets are used in optimization problems such as clustering and partitioning, where elements need to be grouped into disjoint sets based on certain criteria to optimize objectives like resource allocation or load balancing.

Frequently asked question

What is union-find in algorithm?

Union-Find, also known as disjoint set data structure, is used to efficiently manage disjoint sets of elements. It supports two main operations: union, which merges two sets, and find, which determines the set to which an element belongs.

What is union-find in Kruskal's algorithm?

In Kruskal's algorithm for finding the minimum spanning tree of a graph, the union-find data structure is used to efficiently determine whether adding an edge creates a cycle in the spanning tree. This is achieved by maintaining disjoint sets for the vertices and merging sets of connected vertices during the algorithm's execution.

What is the merge union-find algorithm?

The Merge Union-Find algorithm is an alternative implementation of the union-find data structure that uses a more efficient approach for the union operation. It employs path compression and union by rank optimizations to ensure efficient merging of sets and fast find operations.

What is union-find in a matrix?

Union-Find in a matrix refers to using the union-find data structure to efficiently manage connected components in a matrix or grid. It helps determine connectivity between elements in the matrix, facilitating tasks like identifying islands in a grid or solving percolation problems in computer science and physics.

Conclusion

In this article, we learned about the Disjoint Set (Union Find Algorithm). The Disjoint Set data structure, also known as the Union-Find algorithm, stands as a powerful tool in computer science, offering efficient solutions to various problems requiring management of disjoint sets and connectivity queries. From graph algorithms like Kruskal's minimum spanning tree to dynamic connectivity problems and image processing tasks, the versatility of Union-Find finds applications across diverse fields. 

We hope this blog has helped you enhance your Union Find knowledge. Check out our articles to learn more about the Kruskal’s algorithm, Basics of C++, and real-world API. Practice makes a man perfect. 

Happy Coding!