# Union-find approach - weighted quick-union

## Example implementation

The only difference between this and quick-union is the addition of the `sz[]` array, which counts the number of objects in the tree rooted at `i`

``````public class WeightedQuickUnionUF
{
private int[] id;
private int[] sz;

public WeightedQuickUnionUF(int N)
{
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++)
{
id[i] = i;
sz[i] = 1;
}
}

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);
if (i == j) return;
if (sz[i] < sz[j])
{
id[i] = j;
sz[j] += sz[i];
} else
{
id[j] = i;
sz[i] += sz[j];
}
}
}
``````
• This approach improves upon quick-union:
• `Find`: time is proportional to depth of `p` and `q`
• `Union`: constant time, given roots
• the depth of the tree will always be equal to or less than `log2 N`

Cost:

• `new`: `N`
• `Union`: `log2 N` (including cost of finding roots)
• `Find`: `log2 N`

## Another improvement: path compression

• upon computing `root(p)`, simply set the `id` of each visited node to point to that root
• this lets us circumvent the internal cost of `root()` by essentially memoizing the operation
• Implementations:
• “two-pass”:
• add second loop to `root()` to set the `id[]` of each visited node to the root
• “one-pass” (simpler):
• make every other node in the path point to its grandparent (cuts the path length in half)
• both implementations let us keep the tree flat, which makes things easier
• cost is improved dramatically to near linear-time
• with path-compression, weighted quick-union allows 10^9 unions on 10^9 objects to be executed in 6 seconds
• shows the value of a good algorithm!