Union Find

1. dynamic connectivity
2. quick find
3. improvements
   • weight
   • path compression
4. application

LeetCode:

• 200. Number of Islands (Medium)
• 130. Surrounded Regions (Medium)
• 128. Longest Consecutive Sequence (Hard)

Given a set of N objects:

• Union command: replace components containing two objects with their union
• Find query: check if two objects are in the same component.

"is connected to":

• reflexive: every object connects to itself
• symmetric: conn(p,q) is equal to conn(q,p)
• transitive: conn(p,q) and conn(q,r), then conn(p,r)

dynamic connectivity

Union-find data type

public class UF {
  UF(int N) // initializ union-find data structure with N objects
  void union(int p, int q) // add connection between p and q
  boolean connected(int p, int q) // are p and q in the same component?
}

public static void main(String[] args)
{
  int N = StdIn.readInt();
  UF uf = new UF(N);
  while(!StdIn.readInt()) 
  {
    int p = StdIn.readInt();
    int q = StdIn.readInt();
    if (!uf.connected())
    {
       uf.union(p, q);
       StdOut.printIn(p + " " + q);
    }
  }
}

quick find

Find. Check if p and q have the same id

Union. To merge components containing p and q, change all entries whose id equals id[p] to id[q]

O($$N^2$$$$)$$: N union commands on N objects

public class QuickFindUF
{
  private int[] id;
  public QuickFindUF(int U)
  {
    id = new int[N];
    // set id of each object to itself
    for (int i = 0; i < N; ++i)
      id[i] = i;
  }

  public boolean connected(int p, int q) 
  { return id[p] == id[q]; }

  public void union(int p, int q)
  {
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i < N; ++i)
      if (id[i] == pid) id[i] = qid;
  }

}

quick union

id[i] is parent of i, root of i is id[id[id[..id[i]..]]]

Union. To merge components containing p and q, set the id of p's root to the id of q's id.

In worst case:

public class QuickUnionUF
{
  private int[] id;
  public QuickUnionUF(int U)
  {
    ...
  }

  // chase parent pointers until reach root
  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; // change root of p to point to root of q
  }

}

improvements

weighted quick-union

• link root of smaller tree to root of larger tree
• avoid tall tree

Running time:

• Find. takes time proportional to depth of p and q.
• Union. takes constant time, given roots

public class QuickUnionUF
{
  private int[] id, sz;
  public QuickUnionUF(int U)
  {
    id = new int[N];
    // set id of each object to itself
    for (int i = 0; i < N; ++i) {
      id[i] = i;
      sz[i] = 1;
    }
  }

 ...

  public void union(int p, int q)
  {
    int i = root(p);
    int j = root(q);
    if (i == j) return;
    if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
    else { id[j] = i; sz[i] += sz[j]; }
  }

}

path compression

M union-find ops on N objects: O(N+Mlog*N)

keep tree flat:

• Two-pass implementation: after computing the root of p, set the id of each examined node to that root. add second loop.
• Simpler one-pass variant: Make every node in path point to its grandparent (thereby halving path length).

  private int root(int i)
  {
    while (i != id[i]) {
      id[i] = id[id[i]];
      i = id[i];
    }
    return i;
  }

application

percolation