Equivalence Class

See http://www.wikipedia.org/wiki/Equivalence_class

Is there a data structure that can Canonify, Enumerate, and Disconnect equivalence classes ?

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/equivalence.html

I fail to see the problem. You're happy with a solution for dense sets using an array A. For sparse sets, make A a hash, and you're done. It doesn't matter whether the set is large or not given the way you stated things, since obviously you can't achieve the stated goals in less than O(size of set).