Union-Find
1. dynamic connectivity problem
connected component
find query: check if two objects are in the same component
union command:
Union-find data type (API)
- Design an efficient data structure for union-find
2. Quick-Find (eager algorithm)
- an algorithm for solving the dynamic connectivity problem
Data Structure
- integer array id[] of size N
- p and q are connected iff they have the same id (p&q are index, id is value)
Find
- check if q and p have the same id
- id[6]=0; id[1]=1, 6 and 1 are not connected
Union
- to merge components containing q and p, change all entries whose value equals id[p] to id[q]
Cons
- a problem when we have a huge number of objects because there's a lot of values that can change.
- union operation is too expensive