num::concepts::equivalence_relation

Defined in header <structures/concepts.hpp>

template <typename T, typename Index = num::idx>
concept equivalence_relation = requires(T ds, Index u, Index v) {
  { ds.find(u) } -> std::same_as<Index>;
  { ds.unite(u, v) } -> std::same_as<bool>;
  { ds.connected(u, v) } -> std::same_as<bool>;
  { ds.count() } -> std::same_as<Index>;
  { ds.size() } -> std::same_as<Index>;
};

Equivalence relation \(\sim\) on \(\{0,\dots,N-1\}\) with its quotient set.

find(u) selects the canonical representative of \([u]\) and is therefore idempotent. connected(u,v) decides \(u \sim v\) and must agree with \(\mathrm{find}(u) = \mathrm{find}(v)\). unite(u,v) replaces \(\sim\) by the finest relation containing it in which \(u \sim v\). count() is the size of the quotient and drops by one per successful unite.