210. What is an equivalence relation, and how does it relate to disjoint sets?
EasyDisjoint sets
Technical
Show model answer
A relation R is an equivalence relation if it is reflexive (a R a), symmetric (a R b implies b R a) and transitive (a R b and b R c imply a R c). Examples: being in the same connected component, having the same remainder mod m, or being the same person in deduplicated records.
An equivalence relation partitions its elements into disjoint equivalence classes. The union-find (disjoint set) structure maintains exactly such a partition dynamically: union merges two classes when a new equivalence is learned, and find returns a canonical representative so two elements are equivalent if and only if they have the same representative.