# 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:**

**Output:**

### Example 2

**Source Code:**

**Output:**

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

## 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.