Does this code outperform the common implementation with path-compression and union-by-rank? I'm still okay with a review.
import java.util.*;
public class DisjointSet<E> {
public static void main(String... args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
DisjointSet<String> set = new DisjointSet<>();
for (int i = 0; i < n; i++) {
String a = s.next();
String b = s.next();
set.union(a, b);
}
System.out.println(set);
}
/**
* a map from each element to a reference to the set
* that contains them. The reference is used so that many
* map entries can be updated at once in O(1) without
* the cost of iterating through each entry.
* This occurs when performing the union. If we are merging
* a set A and a set B then we would otherwise be required
* to iterate through all of B's entries and point them to
* A and then call A.addAll(B). By having a mutable reference
* we skip the iteration and update all entries of B in O(1).
*/
private HashMap<E, Ref<Set<E>>> map = new HashMap<>();
/**
* a set of references to subsets.
* Just used for #toString().
*/
private Set<Ref<Set<E>>> refs = new HashSet<>();
/**
* @time worst case O(n), amortised O(1)
*/
public void union(E a, E b) {
Ref<Set<E>> ra = map.get(a);
Ref<Set<E>> rb = map.get(b);
Set<E> sa = ra != null ? ra.value : null;
Set<E> sb = rb != null ? rb.value : null;
Set<E> t;
if (sa == null && sb == null) {
t = new HashSet<>();
t.add(a);
t.add(b);
} else if (sa != null && sb != null) {
t = sa.size() > sb.size() ? sa : sb;
// addAll is worst-case O(n) but you have to add n items to be able to
// experience that worst case, and all intermediate adds will be O(1),
// so #union is amortised O(1)
t.addAll(sa.size() > sb.size() ? sb : sa);
} else {
t = sa != null ? sa : sb;
t.add(a);
t.add(b);
}
Ref<Set<E>> ref = ra != null ? ra : rb != null ? rb : new Ref<>();
ref.value = t;
map.put(a, ref);
map.put(b, ref);
refs.remove(ra);
refs.remove(rb);
refs.add(ref);
}
/**
* @param e the element whose (sub)set you would like to find.
* @return the set that e belongs to or null if it is not present
* @time O(1)
*/
public Set<E> find(E e) {
Ref<Set<E>> ref = map.get(e);
return ref != null ? ref.value : null;
}
/**
* @time O(n)
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (Ref<Set<E>> ref : refs) {
builder.append(ref.value);
builder.append('\n');
}
return builder.toString();
}
private class Ref<R> {
private R value;
Ref(R r) {
value = r;
}
public Ref() {
}
}
}