# 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

- each index of

- interpretation:
`id[i]`

is parent of`i`

- root of
`i`

is`id[id[id[...id[i]...]]]`

- integer array

```
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`)
```

`Find`

:- Check if
`p`

and`q`

have the same root

- Check if
`Union`

:- To merge components containing
`p`

and`q`

, set the`id`

of`p`

’s root to the`id`

of`q`

’s root

- To merge components containing

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