Disjoint set (Union find Algorithm)

Introduction

In this blog, we will discuss the union-find algorithm. But before moving further we need to understand the meaning of a disjoint set. We can call two sets as disjoint if the intersection of two sets is an empty set. In other words, there is no common element between the two sets.

The union find is also known as set union. The disjoint-set data structure is a type of data structure that maintains a set of elements partitioned into a number of disjoint subsets. The union find algorithm is used to perform the following operations:

• Find operation: This operation is used to determine which subset a particular element belongs to. It can also be used to determine whether two elements belong to the same set.
• Union operation: The union operation is used to join two elements or subsets in a single subset. But before performing union operations we need to find whether two subsets belong to the same set.

Examples

Let us consider the following example:

Union(1, 2)

Since, 1 and 2 do not belong to the same subset already therefore we can perform the union operation to unite them. After union, both 1 and 2 belong to the same set:

Union(2, 3)

Since, 2 and 3 do not belong to the same subset already therefore we can perform the union operation to unite them. After union, both 2 and 3 belong to the same set:

As you can see above, now all the three elements: 1, 2 and 3 belong to the same set.

Determining cycle in a graph

You are given a graph and you need to determine whether the graph contains a cycle or not.

Input 1:

Output 1:

Cycle exist in the graph

Input 2:

Output 2:
Cycle exist in the graph

Algorithm

Follow the below steps to implement the intuition:

• Initially create a parent[] array and track all the subsets.
• Now traverse to all the edges:
• Check to which subset each of the nodes belong to by finding the parent[] array till the node and the parent are the same.
• If there are two nodes that are already part of the same subset then there exists a cycle. Therefore, print â€śCycle exists in the graphâ€ť
• Otherwise, perform union operation on those two nodes or subsets.
• If no cycle is found, print â€śCycle doesnâ€™t exist in the graphâ€ť.

The implementation of the approach is given below:

Example 1

Source Code:

 #include using namespace std;// Edge classclass Edge {public:    int u, v;};  // A class to represent a graphclass Graph {public:    // "vertices" represents the total number of vertices    // "edges" represents the total number of edges    int vertices, edges;      // Graph is represented as an array of edges    Edge* edge;};  // Creates a graph with V vertices and E edgesGraph* constructGraph(int vertices, int edges){    Graph* graph = new Graph();    graph-> vertices = vertices;    graph->edges = edges;      graph->edge = new Edge[graph-> edges * sizeof(Edge)];      return graph;}  // A utility function to find the subset of an element iint find(int parent[], int u){    if (parent[u] == u)        return u;    return find(parent, parent[u]);}  // A utility function to do union of two subsetsvoid unionNodes(int parent[], int u, int v) { parent[u] = v; }  int checkCycle(Graph* graph){    // Allocate memory for creating V subsets    int* parent = new int[graph-> vertices * sizeof(int)];      // Initialize with the self parent initially    for(int index = 0; index < sizeof(int) * graph -> vertices; index++) {        parent[index] = index;    }      // Iterate over the edges    for (int index = 0; index < graph-> edges; ++index) {        int parent1 = find(parent, graph->edge[index].u);        int parent2 = find(parent, graph->edge[index].v);          if (parent1 == parent2)            return 1;          unionNodes(parent, parent1, parent2);    }    return 0;}int main() {        int vertices = 4, edges = 4;        // Construct the graph    Graph* graph = constructGraph(vertices, edges);      // add edge 0-1    graph->edge[0].u = 0;    graph->edge[0].v = 1;      // add edge 1-2    graph->edge[1].u = 1;    graph->edge[1].v = 2;      // add edge 2-3    graph->edge[2].u = 2;    graph->edge[2].v = 3;    // add edge 3-0    graph->edge[3].u = 3;    graph->edge[3].v = 0;        // add edge 3-4    graph->edge[4].u = 4;    graph->edge[4].v = 0;          if (checkCycle(graph))        cout << "Cycle exists in the graph";    else        cout << "Cycle doesn't exist in the graph";      return 0;}

Output:

Example 2

Source Code:

 #include using namespace std;// Edge classclass Edge {public:    int u, v;};  // A class to represent a graphclass Graph {public:    // "vertices" represents the total number of vertices    // "edges" represents the total number of edges    int vertices, edges;      // Graph is represented as an array of edges    Edge* edge;};  // Creates a graph with V vertices and E edgesGraph* constructGraph(int vertices, int edges){    Graph* graph = new Graph();    graph-> vertices = vertices;    graph->edges = edges;      graph->edge = new Edge[graph-> edges * sizeof(Edge)];      return graph;}  // A utility function to find the subset of an element iint find(int parent[], int u){    if (parent[u] == u)        return u;    return find(parent, parent[u]);}  // A utility function to do union of two subsetsvoid unionNodes(int parent[], int u, int v) { parent[u] = v; }  int checkCycle(Graph* graph){    // Allocate memory for creating V subsets    int* parent = new int[graph-> vertices * sizeof(int)];      // Initialize with the self parent initially    for(int index = 0; index < sizeof(int) * graph -> vertices; index++) {        parent[index] = index;    }      // Iterate over the edges    for (int index = 0; index < graph-> edges; ++index) {        int parent1 = find(parent, graph->edge[index].u);        int parent2 = find(parent, graph->edge[index].v);          if (parent1 == parent2)            return 1;          unionNodes(parent, parent1, parent2);    }    return 0;}int main() {        int vertices = 3, edges = 2;        // Construct the graph    Graph* graph = constructGraph(vertices, edges);      // add edge 0-1    graph->edge[0].u = 0;    graph->edge[0].v = 1;      // add edge 1-2    graph->edge[1].u = 1;    graph->edge[1].v = 2;      if (checkCycle(graph))        cout << "Cycle exists in the graph";    else        cout << "Cycle doesn't exist in the graph";      return 0;}

Output:

As you can see in the output, there doesnâ€™t exist any cycle in the graph.

write your code here: Coding Playground

Conclusion

In this blog, we discussed the union find algorithm. We also illustrated its implementation in C++. We believe that this blog has been interesting for you.