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++ implementation –
 

Download   Run Code

Output:

Cycle Found

 
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

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Abhishek
Guest
Abhishek

Graph in the question/heading is undirected graph, whereas the graph in implementation is directed

wpDiscuz