CSCI2100 · Theorem · Chapter 1 · Disjoint sets
Union–find tracks incremental connectivity
2 steps of prerequisites below it
If every arriving edge (u,v) is processed by unite(u,v), then after each edge two vertices have equal representatives exactly when the processed edges connect them.
Taught in
Uses
- Disjoint-set operations · used in its proof, proof step 1.1
Used by
No later knowledge point in these notes uses it.
Counterexamples
Everything this builds on, earliest first · 2 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Partition · 1.1
- Disjoint-set operations · 1.1
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.