Disjoint Set¶

Equivalence Relations¶

• 等价关系（equivalence relation）是满足以下三个性质的二元关系：

  1. 自反性（reflexivity）：对于任意元素 \(a\)，都有 \(a \sim a\)
  2. 对称性（symmetry）：对于任意元素 \(a\) 和 \(b\)，如果 $a \sim b $，则 \(b \sim a\)
  3. 传递性（transitivity）：对于任意元素 \(a\)、\(b\) 和 \(c\)，如果 \(a \sim b\) 且 \(b \sim c\)，则 \(a \sim c\)

• 等价类（equivalence class）：对于一个元素 \(a\)，与 \(a\) 等价的所有元素组成的集合称为 \(a\) 的等价类，记为 \([a]\)。即 \([a] = \{ x \mid x \sim a \}\)

HW7 -- Union-Find¶