Algorithm: Union-Found

Link for google slides: https://docs.google.com/presentation/d/19smlun4_s920BNbmnguV2y3ZVOYfIG9gsXfJ83Nbjbs/edit#slide=id.ge7b5133482_0_0

Union Find (Disjoint Set)  

Union-find provides near-constant-time operations to add new sets, merge existing sets, and determine whether elements are in the same set.

‍

Basic Idea of Union Find

Union Find:

• Find: To find the subset a particular element 'k' belongs to. It is generally used to check if two elements belong to the same subset or not.
• Union: It is used to combine two subsets into one. A union query, say Union(x, y) combines the set containing element x and the set containing element y.

‍

Naive implementation: 

• Built a global array/list of size n to keep track of the parent. 
• Find(u) : If parent[u]=u then we will return parent[u] in the other case we will recursively find the parent of parent[u] until the condition parent[u]=u satisfies.
• Union(u, v) Find parents of u and v. If they found different,  then we would merge them by making parent[u]=v or parent[v]=u.

‍

Improvement of Union Find

Optimization 1 (Weighting):

Attach the tree with a lower rank(shallow tree) to the tree with a higher rank. and the ideal combined tree would be a larger tree to absorb a smaller tree.

The change in the algorithm of the union function is as follows:

• Check which set has a greater rank then we will attach a lower rank tree to the tree with a higher rank.
• If trees have equal rank then we only need to increase the rank of the tree to which the other is joined by one.

‍

Optimization 2 (Path Compression):

‍

‍

To shorten the path to the parent of all those intermediate nodes by directly connecting them to the leader of the set.

Modify our find function when finding the parent of parent[u] we will also pass the result to parent[u] .

‍

Application of Union Find

Complexity Analysis of Most Optimized Approach:

• It is used to find Cycle in a graph as in Kruskal's algorithm, DSUs are used.
• Checking for connected components in a graph.
• Searching for connected components in an image.

‍

Bibliography

1. “Disjoint set (or Union-Find): Set 1 (detect cycle in an undirected graph),” GeeksforGeeks, 21-Jul-2022. [Online]. Available: https://www.geeksforgeeks.org/union-find/. [Accessed: 01-Aug-2022]. 
2. K. Wayne and R. Sedgewick, “Dynamic connectivity.,” Princeton University, 14-Sep-2019. [Online]. Available: https://algs4.cs.princeton.edu/15uf/. [Accessed: 01-Aug-2022]. 
3. R. Hsu, “Weighted Quick-Union and path compression,” Medium, 05-Jul-2021. [Online]. Available: https://medium.com/datascienceray/quick-union-improvement-6798449e2781. [Accessed: 01-Aug-2022]. 
4. M. Phan, “Quick Union,” Manh Phan - Practice makes perfect!, 20-Mar-2019. [Online]. Available: https://ducmanhphan.github.io/2019-03-20-Quick-Union/. [Accessed: 01-Aug-2022]. 
5. W. Fiset, “Union find - union and find operations,” YouTube, 07-Apr-2017. [Online]. Available: https://www.youtube.com/watch?v=0jNmHPfA_yE&ab_channel=WilliamFiset. [Accessed: 01-Aug-2022]. 
6. W. Fiset, “Union find Kruskal's algorithm,” YouTube, 07-Apr-2017. [Online]. Available: https://www.youtube.com/watch?v=JZBQLXgSGfs&ab_channel=WilliamFiset. [Accessed: 01-Aug-2022]. 

‍