Datenstruktur zur Gruppierung der Elemente von Äquivalenzklassen

Question

Ich muss eine Datenstruktur implementieren, die die Elemente einer Äquivalenzklasse gruppiert.

Die API:

interface Grouper<T>{
  void same(T l, T r);
  Set<EquivalenceClass<T>> equivalenceClasses();
}

interface EquivalenceClass<T>{
    Set<T> members();
}

Zum Beispiel verhält sich die Gruppierung wie folgt:

Grouper g;
g.same(a, b);
g.equivalenceClasses() -> [[a,b]]

g.same(b, a);
g.equivalenceClasses() -> [[a,b]]

g.same(b, c);
g.equivalenceClasses() -> [[a,b,c]]

g.same(d, e);
g.equivalenceClasses() -> [[a,b,c], [d,e]]

g.same(c, d);
g.equivalenceClasses() -> [[a,b,c,d]]

Ich bin auf der Suche nach einer Implementierung, die bis zu ~10 Millionen Einträgen funktioniert. Sie sollte optimiert sein, um sie zu füllen und die Äquivalenzklassen einmal zu erhalten.