280. Graph – Find Cycle in Undirected Graph using Disjoint Set (Union-Find)

Objective: Given a graph, check if the graph contains a cycle using a disjoint set.

Note: Disjoint-set data structure, also called a union–find data structure or merge–find set.

Example:

Earlier in Detect Cycle in Undirected Graph using DFS we discussed how to find cycles in graphs using DFS. In this article we will discuss how to find a cycle using a disjoint set.

It is strongly recommended to read “Disjoint-set data structure” before continue reading this article.

How to find the cycle:

1. The makeset operation makes a new set by creating a new element with a parent pointer to itself.
2. Then process each edge of the graph and perform find and Union operations to make subsets using both vertices of the edge.
3. If the find operation on both the vertices returns the same parent (which means both vertices belong to the same subset) then the cycle is detected.

Let's walk through one example for more understanding, see the animation below:

PreviousNext

Output:

Graph contains cycle: true

Ref: wiki

Related Problems:

- Introduction to Bipartite Graphs OR Bigraphs Medium
- Find Nodes at Distance X from a Given Node in a Tree Hard
- Text Justification Problem (OR Word Wrap Problem) - Leetcode 68 Hard
- Convert binary tree to its Sum tree Medium
- Merge or Combine Two Sorted Linked Lists Medium