Quick Union Find

Let’s say you have 9 vials of liquid and the list of pairs to combine as follows:

1 & 2 (new batch)
5 & 8 (new batch)
9 & 4 (new batch)
9 & 6 (new 6 goes into existing 9)
3 & 5 (new 3 goes into existing 5)
7 & 1 (new 7 goes into existing 1)
2 & 5 (combine separate existing batches)
2 & 3 (same batch already)

How many separate batches do you have after each move? Are 2 & 4 in the same one?

Solution

This is solved with a Quick Union data structure; this structure has the following operations:

insert(a, b) Ensures two IDs exist in the same set

find(a) This belongs to which set?

count() How many total sets?

Where m = links_num and n = items_num, the running time is O(m lg n).

My implementation is in git and below:

Leave a Reply