用于对等价类的元素进行分组的数据结构

Question

我必须实现一个数组结构,该结构将等价类的元素分组.

API:

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

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

例如,分组行为如下:

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]]

我正在寻找一个可以达到约1000万条目的实现.它应该被优化以填充它并获得一次等价类.

Answer 1

看看Union-Find.联合("相同")可以简单地完成O(log N),并且可以通过O(1)一些优化有效地完成."equivalenceClasses"是O(N),无论如何都要访问所有内容的成本.