The "lazy" algorithm for tackling the Dynamic Connectivity problem.

0-quick-union.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton). A setup of the the Dynamic Connectivity problem is explained here.

##Quick Union We know from the Dynamic Connectivity setup that points with the same roots are connected. We also know that all points within a tree (or connected component) share the same root. So two points - and therefore two trees - can be connected by making their roots equal. The root of the one point is set as the root of the second point.

To check if two points are connected, their roots are compared. To check a root, we keep 'following' id-array elements until the id-array element matches its point.

point array  [1][2][3]
id array     [3][2][2]

If we want the root of 1, we check its id-array element, which is 3. The id-array element of 3 is 2. The id-array element of 2 is 2, and so 2 is the root.

If you have a long path - if your tree is "tall" - it can take a lot of time to find roots.

####Example starting from:

point array  [1][2][3][4][5][6][7][8][9]
id array     [2][2][3][7][2][3][7][2][8]

  2     3   7
 /|\    |   |
1 5 8   6   4
    |
    9

connecting 2 & 3 gives:

point array  [1][2][3][4][5][6][7][8][9]
id array     [2](3)[3][7][2][3][7][2][8]

    3     7
   / \    |
  2   6   4
 /|\
1 5 8
    |
    9

Advantages Fast connect/union, as only need to change one element of the id array.

Disadvantages If trees are tall, it can take long to find the roots of elements.

####TLDR Check-connected: check if roots are equal Connect p & q: set the root of p equal to the root of q. Too slow.

QuickUnionUF.java

public class QuickUnionUF{
	private int[] id;

	public QuickUnionUF(int N)
	{
		id = new int[N];

		for (int i = 0; i < N; i++){
			id[i] = i;		
		}
	}

	public boolean connected(int p, int q)
	{
		return root(p) == root(q);
	}

	public int root(int p)
	{
		while(id[p] != p){
			p = id[p];
		}
		return p;
	}

	public void union(int p, int q)
	{
		id[root(p)] = root(q);
	}

	public void printID()
	{
		StdOut.print("ID array ");
		for (int i = 0; i < id.length; i++)
			StdOut.print("[" + id[i] + "] ");
		StdOut.println("");
	}
}