Union Find

Operations

1. Find(x): find rot/clusterId -> O(n)
2. Union(x,y): merge two clusters -> O(1)

Features

1. Check whether two elements are in the same set in O(1)
2. Optimization:
   • Path Compression: make tree flat -> happen during Find()
   • Union by rank: merge low rank tree to high rank tree