# 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

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.

Output:

Cycle Found

## Java

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.

(2 votes, average: 5.00 out of 5)

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 🙂

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.