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