Skip to content

Union-find approach - quick-union

Union-find approach - quick-union

id[10]{0, 1, 9, 4, 9, 6, 6, 7, 8, 9}

// root of `3` is `9` (`id[3]` is `4`, `id[4]` is `9`)

Example implementation

public class QuickUnionUF
{
  private int[] id;
  
  public QuickUnionUF(int N)
  {
    id = new int[N];
    for (int i = 0; i < N; i++) id[i] = i;
  }
  
  private int root(int i)
  {
    while(i != id[i]) i = id[i];
    return i;
  }
  
  public boolean connected(int p, int q)
  {
    return root(p) == root(q);
  }
  
  public void union(int p, int q)
  {
    int i = root(p);
    int j = root(q);
    id[i] = j;
  }
}

Problem: too slow

Cost: