Definition

Union Find, also known as the Disjoint Sets data structure, is used to manage a collection of disjoint sets. It's particularly useful for problems involving connected components in a graph, such as cycle detection or finding the number of connected components. While it's technically a tree data structure, it's mostly applied to graphs. Here's a summary of the main points:

1. Concept:
   • Union Find helps manage multiple disjoint sets and supports two primary operations: find and union.
   • find determines the set a particular element belongs to, and union merges two sets.
2. Applications:
   • Useful for determining connected components in a graph.
   • Can detect cycles in a graph.
3. Operations:
   • Initialization: Each element starts as its own parent, forming its own set.
   • Union: Merges two sets by connecting the root of one tree to the root of another, often using union by rank (merging smaller trees under larger trees to keep the structure balanced).
   • Find: Locates the root of a set, with path compression optimizing future queries by making nodes point directly to the root.
4. Optimizations:
   • Union by Rank: Keeps the tree shallow by attaching shorter trees under the root of taller trees.
   • Path Compression: Flattens the structure of the tree whenever find is called, making future operations faster.
5. Time Complexity:
   • Without optimizations, find can be O(n).
   • With union by rank or path compression, the complexity improves to O(log n).
   • With both optimizations, the amortized time complexity for each operation becomes nearly constant, represented by the inverse Ackermann function, which is very efficient in practice.
6. Example:
   • Given a graph, initialize each node as its own set.
   • For each edge, use union to merge sets.
   • Use find to check if two nodes are already connected, which helps in cycle detection or counting connected components.

Union Find is an efficient and powerful data structure for specific graph-related problems, especially when handling large datasets where operations need to be optimized for performance.

Example

Sure, let’s walk through the example visually step by step.

Initial Setup

We have 4 nodes: 1, 2, 3, 4 Each node starts as its own parent (self-rooted).

Initial state:

• parent = {1: 1, 2: 2, 3: 3, 4: 4}
• rank = {1: 0, 2: 0, 3: 0, 4: 0}

Union Operations

Let's add the edges (1, 2), (2, 4), and (4, 1) step-by-step.

1. Union(1, 2)

• Find roots:
  • Root of 1: 1 (itself)
  • Root of 2: 2 (itself)