One Pager Cheat Sheet

• In this lesson, we'll learn about how to use the Union-Find algorithm to solve the problem of network connectivity by exploring graphs and optimizing for efficiency.
• The Union-Find algorithm is an algorithmic technique that keeps track of a set of elements partitioned or split into a number of disjoint (non-overlapping) subsets and uses the Find and Union methods to determine if two elements are in the same subset and model the actual connection/path between the two objects.
• You can apply the Union-Find algorithm on disjoint subsets to find and union elements, efficiently solving problems such as determining if a graph is cyclic or not.
• A real-world example of the Union-Find algorithm involves creating subsets for each edge in order to determine if two vertices of the same vertices belong to the same subset, thereby confirming the presence of a cycle.
• We will loop through the edges to check if the graph is cyclic or not, and if it is acyclic, our parent array representation will show the final subsets.
• Using the array indices as IDs, we are modeling parent-child relationships between the edges, and by changing the the value at index 0 to 1, we are saying 0 is the parent of 1 which is now representative of the union set Union(0, 1).
• We need to union the sets and replace -1 with 2 to indicate the change, then take the edge connecting 1 and 3.
• Replace -1 in 2 with 3, merge the sets of 1, 2 and 3, 4, and take the edge connecting 1 and 4.
• The two elements 3 and 4 are in different sets so we need to union them to create a single edge between them.
• The Union-Find algorithm requires optimizations like path compression, union by rank and union by size to achieve O(n) time for the Union and Find operations.
• The Union-Find algorithm, which can be optimized with techniques such as path compression and union by rank, is commonly used to perform merge-operations.