What are operations on Disjoint set in DAA?

Disjoint Set Operations in DAA

There are 2 major disjoint set operations in daa: 

1. Union/Merge - this is used to merge 2 subsets into a single subset.
2. Find - This is used to find which subset a particular value belongs to.

We will take a look at both of them. To make things easier, we will change our sets from integers to Cities. 

Let's say this Data Structure represents the places connected via express trains/ metro lines or any other means. 

Union/Merge

Suppose, in our example - a new express train started from Delhi to Agra. This would mean that all the cities connected to Delhi are now connected to all the cities connected to Agra. 

This simply means that we can merge the subsets of Agra and Delhi into a single subset. It will look like this. 

One key issue here is which out of Agra and Delhi will be the new Parent? For now, we will just choose any of them, as it will be sufficient for our purposes. Let's take Delhi for now. 

Further optimizations can be made to this by choosing the parent based on which subset has a larger number of values.

This is the new state of our Disjoint Set Data Structure. Delhi is the parent of Delhi, Gurgaon, Noida, Agra, Vrindavan, and Mathura.

This would mean that we would have to change the parent of Agra, Vrindavan, and Mathura (basically, all the children of Agra), to Delhi. This would be linear in time. If we perform the union operation m times, and each union takes O(n) times, we would get a quadratic O(mn) time complexity. This is not optimized enough.

Instead, we structure it like this:

Earlier, Agra was its own parent. Now, Delhi is the parent of Agra. 

Now, you might be wondering - The parent of Vrindavan is still Agra. It should have been Delhi now. 

This is where the next operation helps us - the find operation.

Find

The find operation helps us find the parent of a node. As we saw above, the direct parent of a node might not be its actual (logical) parent. E.g., the logical parent of Vrindavan should be Delhi in the above example. But its direct parent is Agra. 

So, how do we find the actual parent?

The find operation helps us to find the actual parent. In pseudocode, the find operation looks like this:

find(node):

if (parent(node)==node) return node;

else return find(parent(node));

We don't return the direct parent of the node. We keep going up the tree of parents until we find a node that is its own parent. 

Let's understand this via our example. 

Suppose we have to find the parent of Mathura. 

1. Check the direct parent of Mathura. It's Agra. Is Agra == Mathura?
   The answer is false. So, now we call the find operation on Agra. 
2. Check the direct parent of Agra. It's Delhi. Is Delhi ==Agra?
   The answer is false. So now we call the find operation on Delhi.
3. Check the direct parent of Delhi. It's Delhi. Is Delhi==Delhi.
   The answer is true! So, our final answer for the parent of Mathura is Delhi.

This way, we keep going "up" the tree until we reach a root element. A root element is a node with its own parent - in our case, Delhi.

Let's try to find the parent of K in this example. (A and D are their own parents)

1. ParentOf(K) is I. Is I == K? 
   False. So, we move upward, now using I.
2. ParentOf(I) is C. Is C== I? 
   False. Move upward using C.
3. ParentOf(C) is A. Is A==C?
   False. Move upward using A.
4. ParentOf(A) is A. Is A==A?
   True! Our final answer is A.

Let's understand the use of a Disjoint Set Data Structure through a simple application - Finding a cycle in an undirected graph.

Also see, Morris Traversal for Inorder, hash function in data structure

Find a Cycle in an Undirected Graph using Disjoint Set Data Structure

Let us understand the disjoint set operations in daa more clearly with the help of an example. Here, we will use a disjoint set data structure to find whether an undirected graph contains a cycle or not. We are assuming that our graph does not contain any self-loops. 

Let this be our graph. Each node is initialized as its own parent. The list of edges is shown on the top right, and the parents are shown at the bottom. We have shown each edge only once for simplicity (i.e., 1-2 and 2-1 aren't shown separately)

Algorithm

We will go through each edge and do the following. Let the edge be u-v.

1. Find the parent of u and v. If both parents are the same, it means u and v are part of the same subset, and we have found a cycle.v
2. If they are not the same, merge u and v. We don't merge u and v directly. Instead, we merge the parents of u and v. This ensures that all the siblings of u and all the siblings of v have the same common parent. 

We do this for all edges. 

Walkthrough

1. 1-2 Edge. 

Parent of 1 is 1, parent of 2 is 2. They are different, so we will merge them. Set the parent of 2 as 1 (this is chosen randomly, setting the parent of 1 as 2 would also have been correct ).

2. 1-4 Edge. 
Parent of 1 is 1. Parent of 4 is 4. They are not the same, so merge 1 and 4. Set parent of 4 as 1. 

3.  2-5 Edge. 
The parent of 2 is 1, and the parent of 5 is 5. They aren't the same, so we'll merge them. Set the parent of 5 as 1.

4. 3-6 Edge. 
The parent of 3 is 3, and the parent of 6 is 6. They aren't the same, so we'll merge them. Set the parent of 6 as 3.
 

5. 5-6 Edge. 
The parent of 5 is 1, and the parent of 6 is 3. They aren't the same, so we'll merge them. Set the parent of 3 as 1.

Note here - the direct parent of 6 is still 3. But, the actual parent becomes 1, because the parent of 3 is 1. (The dotted line is not an edge in the graph, it shows that the parent of 3 is 1)
 

6. 6-2 Edge. 
The parent of 6 is 1 (actual parent), and the parent of 2 is also 1. These are both the same. Thus, our graph contains a cycle.

Code in C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

// An edge in the graph
struct Edge {
    // the endpoints of the edge
    int u, v;
    // constructor for Edge
    Edge(int u, int v) : u(u), v(v) {}
};

// This class represents a graph using edge list representation
class Graph {
  public:
    int V;              // no of vertices in the graph
    vector<Edge> edges; // list of edges in the graph
 
    Graph(int v) { // constructor
        V = v;
    }

    // adds an edge (u,v) to the graph
    void addEdge(int u, int v) { edges.push_back(Edge(u, v)); }
};

// A disjoint set data structure that supports merge and find operations
class DisjointSet {
//The array that stores the parents of each node
    vector<int> parent;

  public:
    //the number of nodes
    int V;
    // constructor
    DisjointSet(int V) : V(V) {
        //initialise with V+1 values so our nodes can be 1-indexed
        parent = vector<int>(V + 1);
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }
    }
    //find operation of Disjoint Set Data Structure
    int find(int u) {
        if (u == parent[u])
            return u;
        return find(parent[u]);
    }
    //merge or union operation of Disjoint Set Data Structure
    void merge(int u, int v) {
        int parentU = find(u);
        int parentV = find(v);
        if (parentU != parentV) {
            parent[parentU] = parentV;
        }
    }
};

// function to detect whether cycle exists in graph, using Disjoint Set Data Structure
void cycleExists(Graph g) {
    DisjointSet ds(g.V);
    for (Edge e : g.edges) {
        int u = e.u;
        int v = e.v;
        if (ds.find(u) == ds.find(v)) {
            cout << "Cycle exists between " << u << " and " << v << endl;
            return;
        }
        ds.merge(u, v);
    }
    cout << "No cycle exists" << endl;
}

//main driver function
int main() {
    Graph g(6);
    g.addEdge(1, 2);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(3, 6);
    g.addEdge(5, 6);
    g.addEdge(6, 2);

    cycleExists(g);

    return 0;
}

Output:

Complexities for Disjoint Set Operations in DAA

Regardless of the example or the purpose in which they are used, disjoint set operations in daa always have the same space and time complexities. The complexities for both find and union operations are:

The space complexity is O(n), where n is the number of vertices. The parent array stores the parent of each vertex. Hence we get O(n) space complexity. We aren't considering the space complexity of the graph in this because the graph is the input here.

The time complexity is O(log N) in the average case because the find operation will have to go up a tree with n nodes. The height of a tree in the average case will be log N. In the worst case, we can have a skewed tree, and our time complexity will become O(n). 
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

Is there a way to decrease the time complexity of the disjoint set operations in daa?

Yes, we can perform union by path-compression and rank operations to reduce the time complexity. With this, we don't change how the tree is traversed - but we make sure the skew case can never occur. 

Are disjoint set operations in daa used practically?

Disjoint set operations are optimal and efficient in practical uses. They have a lot of uses in real-life applications - e.g., finding connected components, Kruskal's algorithm, etc.

Why do we merge the parents instead of the actual nodes in the merge operation for a disjoint set?

We merge parents instead of nodes so that all the children of both parents come under a single parent. E.g., let's say we need to merge B and Y. A is the parent of B, and X is the parent of Y. Another node C, also has its parent as A. And another node, Z, also has its parent as Y. If we merge B and Y directly by setting the parent of B as Y - then we will disconnect B from A and from C. However, if we merge A and X, by setting the parent of X as A, then all the nodes (A, B, C, X, Y, Z) will have a single parent A. This is what we want.

Conclusion

In this article, we have discussed the disjoint sets, disjoint set operations in daa, methods to detect a cycle in a graph, and implementation using union-find method in detail. 

After reading about how to find the Closest element to a target value in Binary Search Tree, are you not feeling excited to read/explore more articles on the topic of BST? Don't worry; Coding Ninjas has you covered. If you want to practice questions on the binary tree then follow these links: disjoint set data-structure, Check if two sets are disjoint, union-find algorithm.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!