# Find disjoint sets in a graph using disjoint set ADT operations FIND, UNION

In this article, we are going to see **usage of disjoint set ADT operation to find disjoint sets in a graph**.

Submitted by Radib Kar, on September 11, 2020

**Prerequisite:** ADT set

Let us first discuss what disjoint sets in a graph is? Disjoint sets in a graph mean components of a graph. Each connected component is treated as a disjoint set since it has no relation with the other components. Each connection (edge) is said to be the relation between two nodes. Two nodes having a relation falls in the same set.

In the below input graph,

We have two components and thus two disjoint sets. Those are,

Now, how we can find the disjoint sets. Here comes the find(X) & UNION (X,Y) ADT operation.

The operation finds the set name and here we use array for that. We use a parent array to store all set names initially. Initially all are themselves (i for node i).

We call it a parent array to store the set names:

The algorithm is:

For each edge in the edge list:

If the nodes on the edge are in same set, do nothing, otherwise, we will **UNION** them as they have relations between them and should come under same set.

To check whether the two nodes are in same set we use **FIND**

**Implementation of FIND & UNION **

**1) FIND(X)**

We use a recursive function **find (X, parent [])** to find the set name of element *X*.

The implementation is like below:

FUNCTION find(int X, int parent[]): If(parent[x]==X) return X; return find(parent[x], parent) End FUNCTION

**2) UNION (X, Y)**

Union means we bring both elements under same set which is as simple assigning X as parent of Y

**parent[Y]=X**

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; //FIND(X) int find(int X, vector<int>& parent) { if (parent[X] == X) return X; return find(parent[X], parent); } //UNION(X,Y) void UNION(int X, int Y, vector<int>& parent) { parent[Y] = X; } int main() { int n, m; cout << "Enter number of edges\n"; cin >> n; cout << "Enter number of nodes\n"; cin >> m; //edges list //each edge is a vector [u,v] vector<vector<int> > edges(n); for (int i = 0; i < n; i++) { int u, v; cout << "info for edge " << i + 1 << endl; cout << "Enter source node u: "; cin >> u; cout << "Enter destination node v: "; cin >> v; edges[i] = vector<int>{ u, v }; } vector<int> parent(m + 1); for (int i = 1; i <= m; i++) parent[i] = i; for (auto edge : edges) { //find set name for source node, u int x = find(edge[0], parent); //cout<<x<<endl; //find set name for destination node, v int y = find(edge[1], parent); //cout<<y<<endl; //if they are not in same set already, do their union if (x != y) { UNION(x, y, parent); } } //number of disjoint set is number of -1 in the parent set int count = 0; for (int i = 1; i <= m; i++) if (parent[i] == i) count++; cout << "Number of disjoint set is :" << count << endl; cout << "printing the parent array now:\n"; for (int i = 1; i <= m; i++) cout << parent[i] << " "; cout << endl; return 0; }

**Output:**

Enter number of edges 6 Enter number of nodes 8 info for edge 1 Enter source node u: 1 Enter destination node v: 2 info for edge 2 Enter source node u: 1 Enter destination node v: 3 info for edge 3 Enter source node u: 2 Enter destination node v: 4 info for edge 4 Enter source node u: 2 Enter destination node v: 5 info for edge 5 Enter source node u: 6 Enter destination node v: 7 info for edge 6 Enter source node u: 7 Enter destination node v: 8 Numebr of disjoint set is :2 printing the parent array now: 1 1 1 1 1 6 6 6

**Dry Run for the example:**

So the edge list is:

[ [1, 2],

[1, 3],

[2, 4],

[2, 5],

[6, 7],

[7, 8] ]

We will process each edge one by one and do necessary FIND & UNION

Initially parent[] is:

**Edge 1:**

So source is 1 and destination is 2

We will find parent of both 1 & 2

**Finding parent of 1**

parent[1] is 1 so it returns 1

**Finding parent of 2**

parent[2] is 2 so it returns 2

Since both their set names( parent) are different we do a union

Thus parent[2]=1 now, so after processing **edge 1**

**Edge 2:**

So source is 1 and destination is 3

We will find parent of both 1 & 3

**Finding parent of 1**

parent[1] is 1 so it returns 1

**Finding parent of 3**

parent[3] is 3 so it returns 3

Since both their set names( parent) are different we do a union

Thus parent[3]=1 now, so after processing **edge 2**

**Edge 3:**

So source is 2 and destination is 4

We will find parent of both 2 & 4

**Finding parent of 2**

parent[2] is 1 so it returns find(1, parent) and that returns 1 ultimately (parent[1]== 1)

**Finding parent of 4**

parent[4] is 4 so it returns 4

Since both their set names( parent) are different we do a union

Thus parent[4]=1 now, so after processing **edge 3**

**Edge 4:**

So source is 2 and destination is 5

We will find parent of both 2 & 5

**Finding parent of 2**

parent[2] is 1 so it returns find(1, parent) and that returns 1 ultimately (parent[1]== 1)

**Finding parent of 5**

parent[5] is 5 so it returns 5

Since both their set names( parent) are different we do a union

Thus parent[5]=1 now, so after processing **edge 4**

**Edge 5:**

So source is 6 and destination is 7

We will find parent of both 6 & 7

**Finding parent of 6**

parent[6] is 6 so it returns 6

**Finding parent of 7**

parent[7] is 7 so it returns 7

Since both their set names( parent) are different we do a union

Thus parent[7]=6 now, so after processing **edge 5**

**Edge 6:**

So source is 7 and destination is 8

We will find parent of both 7 & 8

**Finding parent of 7**

parent[7] is 6 so it returns find(6, parents) which ultimately returns 6

**Finding parent of 8**

parent[8] is 8 and thus it returns 8

Since both their set names( parent) are different we do a union

Thus parent[8]=6 now, so after processing **edge 6**

So, the final parent array is:

Hence there are two disjoint sets with parents 1 & 6.

All nodes having same parent fall into same set. So the sets are: **[1, 2, 3,4 5] & [6, 7, 8]**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.