# Union-find approach - quick-find

- 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
- each value in
`id[]`

denotes the root/representative element of the set/component containing that particular object

- interpretation:
`p`

and`q`

are connected if and only if they have the same`id`

- integer array

```
id[10]{0, 1, 1, 8, 8, 0, 0, 1, 8, 8}
// connected sets:
// {0, 5, 6}
// {1, 2, 7}
// {3, 4, 8, 9}
```

`Find`

:- Check if
`p`

and`q`

have the same`id`

- Check if
`Union`

:- To merge components containing
`p`

and`q`

, change all entries whose`id`

==`id[p]`

to`id[q]`

- To merge components containing

## Example implementation

```
public class QuickFindUF
{
private int[] id;
public QuickFindUF(int N)
{
id = new int[N];
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 < id.length; i++)
if (id[i] == pid) id[i] = qid;
}
}
```

## Problem: too slow (algorithm is quadratic)

- for each
`new`

and`union()`

operation, the array is accessed`N`

times (the`for`

loops)- we only use
`init()`

once, but`union()`

is certainly too expensive:`N^2`

array accesses are required to execute`N`

union commands on`N`

objects

- we only use

Cost:

`new`

:`N`

`Union`

:`N`

`Find`

: 1