# 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 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`
``````id{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`
• `Union`:
• To merge components containing `p` and `q`, change all entries whose `id` == `id[p]` to `id[q]`

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

Cost:

• `new`: `N`
• `Union`: `N`
• `Find`: 1