# Finding a cycle in an undirected graph using Disjoint Sets

In this article, we are going to see **how we can use disjoint set ADT to find whether there is a cycle in the undirected graph or not?**

Submitted by Radib Kar, on September 11, 2020

**Prerequisite:**

In the previous article, we saw how we can find a cycle in an undirected graph using DFS? Here we are going to see how we can use disjoint set ADT operation to find whether there is a cycle or not efficiently. If you haven't gone through our articles on disjoint set ADT, please go through the prerequisite articles first to understand this discussion.

In the below example, graph 1 has a cycle where graph2 don't have any cycle.

So, the thing is how we can use disjoint set ADT to find whether there is a cycle or not. As we have discussed in the pre-requisite articles, that an edge is a relation b/w two nodes and two nodes having an edge b/w them, are supposed to be in the same disjoint set. So through our ADT operation FIND(X) & UNION(X, Y), we create disjoint sets out of the available edges. So, to detect a cycle in an undirected graph, we can use the same idea. The algorithm would be:

For each edge in the edge list:

Find parents(set name) of the source and destination nodes respectively **(Though we are using terms like source & destination node, the edges are undirected)**.

If both have the same parent, that means they belong to the same set already and this edge creates a cycle. Since both the node already belong to the same set, that means even without this edge we could have reached one node from other. So the addition of this edge creates a cycle since edges are undirected.

Else

Do the UNION of them to bring them under the same set.

That's so simple!! But only if you have the idea of disjoint set ADT.

Below is the implemenatation.

#include <bits/stdc++.h> using namespace std; int find(int x, vector<int>& parent) { if (parent[x] == x) return x; return find(parent[x], parent); } void UNION(int x, int y, vector<int>& parent, vector<int>& rank) { if (rank[x] > rank[y]) { parent[y] = x; rank[x]++; } else if (rank[x] < rank[y]) { parent[x] = y; rank[y]++; } else parent[y] = x; rank[x]++; } bool isCyclic(vector<vector<int> >& edges, int V) { vector<int> parent(V); for (int i = 0; i < V; i++) parent[i] = i; vector<int> rank(V, 0); for (auto edge : edges) { int x = find(edge[0], parent); int y = find(edge[1], parent); if (x != y) UNION(x, y, parent, rank); else return true; } return false; } int main() { int n, m; cout << "Enter the number of edges\n"; cin >> n; cout << "Enter the 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 }; } if (isCyclic(edges, m)) cout << "There is a cycle in the graph\n"; else cout << "There is no cycle in the graph\n"; return 0; }

**Output:**

RUN 1: Enter the number of edges 6 Enter the number of nodes 6 info for edge 1 Enter source node u: 0 Enter destination node v: 1 info for edge 2 Enter source node u: 0 Enter destination node v: 4 info for edge 3 Enter source node u: 1 Enter destination node v: 3 info for edge 4 Enter source node u: 4 5Enter destination node v: 5 info for edge 5 Enter source node u: 4 Enter destination node v: 2 info for edge 6 Enter source node u: 2 Enter destination node v: 3 There is a cycle in the graph RUN 2: Enter the number of edges 5 Enter the number of nodes 6 info for edge 1 Enter source node u: 0 Enter destination node v: 1 info for edge 2 Enter source node u: 1 Enter destination node v: 3 info for edge 3 Enter source node u: 0 Enter destination node v: 4 info for edge 4 Enter source node u: 4 Enter destination node v: 5 info for edge 5 Enter source node u: 4 Enter destination node v: 2 There is no cycle in the graph

In the above implementation, we see a more efficient implementation of union where we have used "rank of the set". Rank is another array like parent array where we store the height of the tree (which is the root for the set). The motive behind using rank is to balance the heights, otherwise, the complexity for *FIND(X)* will increase.

**Dry Run:**

So the edge list is:

[ [0, 1],

[0, 4],

[1, 3],

[4, 5],

[4, 2],

[2, 3] ]

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

Initially, parent[] is:

**Edge 1:**

So the source is 0 and destination is 1

We will find the parent of both 0 & 1

**Finding parent of 0**

parent[0] is 0 so it returns 0

**Finding parent of 1**

parent[1] is 1 so it returns 1

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

**I am skipping the rank part( you can do that your own)**

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

**Edge 2:**

So the source is 0 and destination is 4

We will find the parent of both 0 & 4

**Finding parent of 0**

parent[0] is 0 so it returns 0

**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]=0 now, so after processing **edge 2**

**Edge 3:**

So the source is 1 and destination is 3

We will find the parent of both 1 & 3

**Finding parent of 1**

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

**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]=0 now, so after processing **edge 3**

**Edge 4:**

So the source is 4 and destination is 5

We will find the parent of both 4 & 5

**Finding parent of 4**

parent[4] is 0 so it returns find(0, parent) and that returns 0 ultimately (parent[0]==0)

**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]=0 now, so after processing **edge 4**

**Edge 5:**

So the source is 4 and destination is 2

We will find the parent of both 4 & 2

**Finding parent of 4**

parent[4] is 0 so it returns 0

**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]=0 now, so after processing **edge 5**

**Edge 6:**

So the source is 2 and destination is 3

We will find the parent of both 2 & 3

**Finding parent of 2**

parent[2] is 0 so it returns find(0, parents) which ultimately returns 0

**Finding parent of 3**

parent[3] is 0 and thus it returns 0

So, that means both of the nodes already belongs to the same set, that means this edge result in a **cycle**.

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.