Clustering Algorithm for a congruence relation?

Question

Say we are given a congruence relation$~\sim$ in a dataset with $n$ elements. I am looking for an algorithm for optimally sorting the $n$ elements into $m$ clusters according to given congruence relations. For instance if the data contains ${a,b,c,d,e,f,g,h}$, and: $$a\sim b,\ d\sim b,\ e \sim h,\ f \sim c$$ The data should be sorted into the following clusters: $$\{a,b,d\},\ \{c,f\},\ \{e,h\},\ \{g\}$$ As said I'm looking for an efficient algorithm to solve this, I am led to believe this can be done in $O(n)$, but I can't seem to work out the details.

Answer 1

I've always heard this referred to as a "Union Find". It's described here, as well as the optimizations you can do to beat the naive implementation: http://www.algorithmist.com/index.php/Union_Find

Answer 2

Write your relation as a sparse graph and use a "connected components" function, like this.