It's possible to maintain the "eclasses" without additional theoretical overhead. Associate a linked list with each representative, initially only containing the representative itself. When you union two representatives, concatenate their linked lists in constant time.