Union-find approach - quick-union
Keywords: | union-find, quick-union, algorithms |
Date: |
- 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 ofi
- root of
i
isid[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
andq
have the same root
- Check if
Union
:- To merge components containing
p
andq
, set theid
ofp
's root to theid
ofq
'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 asN
times
Cost:
new
:N
Union
:N
(including cost of finding roots)Find
:N