Union-Find with Java

There are 4 ways to implement UF, with the most efficient version not so complex compared to the others.

For readers who are not familiar with union-find problem, refer to this article from hackerearth.

Given a list of number pairs, check if the numbers are of the same parent. Initialise id[i] = i (each node is it’s own parent).

1. Quick-find.

public int find(int p) {return id[p];} // O(N)

public void union(int p, int q) { // O(1)
  int pId = find(p), qId = find(q);
  if (pId == qId) return;
  for(int i = 0; i < id.length; i ++) {
    if(id[i] == pId) id[i] = qId;
  }
}

2. Quick-union

// Finding the root of p and q. O(tree height)
public int find(int p) {
  while(p != id[p]) p = id[p];
  return p;
}

public void union(int p, int q) { // O(tree height)
  int pId = find(p), qId = find(q);
  if (pId == qId) return;
  // Note that no loop is needed here since this is finding the root.
  id[pId] = qId;
}

3. Weighted union-find

// Finding the root of p and q. O(lgN)
public int find(int p) {
  while(p != id[p]) p = id[p];
  return p;
}

public void union(int p, int q) { // O(lgN)
  int pId = find(p), qId = find(q);
  if (pId == qId) return;
  // Make the smaller tree point to the larger one.
  if(size[i] < size[j]) {id[i] = j; size[j] += size[i];}
  else {id[j] = i; size[i] += size[j];}
}

4. Compressed path union-find (best and recommended)

// Finding the root of p and q. O(lgN)
public int find(int p) {
  if(p != id[p]) id[p] = find(id[p]);
  p = id[p];
  return p;
}

public void union(int p, int q) { // O(lgN)
  int pId = find(p), qId = find(q);
  if (pId == qId) return;
  // Make the smaller tree point to the larger one.
  if(size[i] < size[j]) {id[i] = j; size[j] += size[i];}
  else {id[j] = i; size[i] += size[j];}
}