Union Find
# Union Find
A data structure to represent dynamic equivalence relations
# Operations
These operations make it an efficient data structure to verify if a cycle exists in some undirected graph.
- Union find is unable to detect cycles in directed graphs: union operation cannot distinguish between the subcomponent that makes the edge from a -> b and that which makes the edge b->a
# Implementations
# Quick Find
# Pseudocode
# Complexity
# Quick Union
Unions are too expensive using quick find, as we have to change the ids of all elements in the combining equivalence class for each union operation.
Improvement: only store the parent of the node
# Pseudocode
# Complexity
# Weighted Quick Union
Quick Union creates possible tall trees as the union operation does not necessarily occur between root nodes.
Improvement: avoid tall trees by linking smaller tree root to larger tree root
# Pseudocode
# Complexity
Hence, besides initialization $O(n)$, all other operations take $O(logn)$
# WQU with Path Compression
Improvement: further reduce the effective path to reach the root node: for some node p which we are computing the root of, we can update id[] of nodes on the path from p to root.
