Data Structures

Disjoint Set


A Disjoint Set data structure keeps track of a set of elements partitioned into a number of disjoint subsets. Disjoint Set supports the following operations:

  • Determine a subset to which a given element belongs. This can be used for determining if two elements are in the same subset.
  • Join two subsets into a one new subset.
  • Create a new subset from the element.
The computational complexity of these operations are near constant. This allows to solve certain problems on Graphs very efficiently. See for example Kruskal's algorithm.


C# implementation - Open on Github

This implementation includes the path compression and union by rank optimizations.



Last updated: 18.12.2020,
created: 23.09.2017.