[7.6] Union Find (Disjoint Set) Algorithm in Python (Detect Cycle in Undirected Graph)

Union Find or Disjoint Set data structure is a data structure that stores collection of disjoint sets(non-overlapping sets).
It has 2 main operations:

1) find - It returns the parent of the subset the given value belongs to
2) Union - It combines the two subsets (by assigning parent of one subset to another)
It has various applications:

1) Kruskal's Algorithm

2) Detect Cycle in a graph

We will learn how to implement union find in python to detect cycle in a graph.

00:00 What is Union Find?
20:17 Detecting Cycle
24:16 Python Program for Union Find

🔗Important Links:

🌐Join our community:

[jonasrl]

Really great video, thank you for visualising the parent array!

[AnimeshSinghIITM]

clearly explained, thanks for making such videos

[varunshrivastava]

I have a couple of doubts when it comes to the implementation that you did in python -
1) On 26:24 you created a parent list and said that the elements that it holds are parents of themselves, But aren't those parents of values that they point to inside the dictionary? Like 0 should be a parent of 1 and 2 and 1 should be a parent of 2.
2) While Implementing FindParent function instead of writing if a == self.parent[a] can I write if a in self.parent[a]?

[shivamdubey]

sir i understood everything but not recursion can you plzz suggest me some videos on it or explain

[sjm]

Is it possible to implement this algorithm without using object oriented features?