Union-Find Algorithm for Cycle Detection in a graph

Given an connected graph, find if it contains any cycle or not using Union-Find algorithm.


 

For example, below graph contains a cycle 8-9-11-12-8

  cycle-depth-first-tree

 
Prerequisite: Disjoint-Set Data Structure (Union-Find Algorithm)

 
We strongly recommend to go through above post to get an understanding on how Union-Find algorithm works. You can also watch first 10 mins of this video to get a clear picture.

 

Complete Algorithm:


1. Create a disjoint sets for each vertex of the graph.
2. For every edge u, v in the graph
   i) Find root of the sets to which elements u and v belongs
   ii) If both u and v have same root in disjoint sets,
       a cycle is found.

 

C++

Download   Run Code

Output:

Cycle Found

Java

Download   Run Code

Output:

Cycle Found

 
The time complexity of Union and Find operation is O(N) in worst case. Please refer implementation of Find and Union discussed in the original post for improving overall time complexity of the algorithm.

 
Also see: Check if an undirected graph contains cycle or not

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Abhishek
Guest

Glad I found this to reiterate what I learned as my algorithms exam is tomorrow 🙂

Smith
Guest

I think in line 90 it should be Union(u, v) and not Union(x, y) because the Find procedure is being called upon these two parameters again.