Given a set $S$ of values, and a set $P \subset S \times S$ of pairwise equivalences, what is an algorithm for partitioning $S$ into equivalence classes?
$P$ is guaranteed to be an equivalence relation.
Assume that $P$ "covers" every member of $S$.
Efficiency isn't all that crucial: I'm interested in $\#S < 100000$ and $\#P < 10000$.
This is like building up pairs into clusters, but because this is for exact equality rather than mere similarity, I'm finding that clustering algorithms are red herrings.
Equivalence classes on the set $S$ are the same as the connected components of the graph whose edges are given by $P$. Fortunately, there are standard algorithms for computing the connected components: here is one example.