6.1. Concept
This section describes disjoint sets
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:
0: {0}
1: {1, 3}
2: {2}
3: {1, 3}
4: {4}
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
.
inSameSet(1, 3) -> true
inSameSet(1, 4) -> false
The union(3, 4)
method joins the two sets including 3
and 4
as one:
0: {0}
1: {1, 3, 4}
2: {2}
3: {1, 3, 4}
4: {1, 3, 4}
If we check if 1
, 3
and 4
are in the same set, it should return true
:
`inSameSet(1, 4)` -> true
`inSameSet(3, 4)` -> true
Last updated
Was this helpful?