# Union-find approach - quick-union

• The data structure for this approach is as follows:
• integer array `id[N]`
• `N` is equal to the number of objects in the disjoint set
• each index of `id[]` corresponds to an object in the disjoint set
• interpretation: `id[i]` is parent of `i`
• root of `i` is `id[id[id[...id[i]...]]]`
``````id{0, 1, 9, 4, 9, 6, 6, 7, 8, 9}

// root of `3` is `9` (`id` is `4`, `id` is `9`)
``````
• `Find`:
• Check if `p` and `q` have the same root
• `Union`:
• To merge components containing `p` and `q`, set the `id` of `p`’s root to the `id` of `q`’s root

## 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

• trees can get very tall
• for each `connected()` (`Find`) operation, the array can be accessed as many as `N` times

Cost:

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