6.1. Concept

A disjoint set enables to be join sets efficiently. There are two methods implemented in this structure, inSameSet() and union().

In the following example, each key in {0, 1, 2, 3, 4} is initially in its own set:

0: {0}
1: {1}
2: {2}
3: {3}
4: {4}

inSameSet(1, 3) checks if the keys 1 and 3 are in the same set:

inSameSet(1, 3) -> false

The union(1, 3) method joins two sets including 1 and 3 as one set:

If we check if the keys 1 and 3 are in the same set, it should return true although for the keys 1 and 4, it should return false.

The union(3, 4) method joins the two sets including 3 and 4 as one:

If we check if 1, 3 and 4 are in the same set, it should return true: