Data Structures

Disjoint Set

Introduction

A Disjoint Set data structure keeps track of a set of elements partitioned into a number of disjoint subsets. It allows to efficiently perform 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 single new subset.
  • Add new subset.
The computational complexity of these operations are near constant. This allows to solve certain problems on Graphs very efficiently.

Implementation

C# implementation with the path compression and union by rank optimizations.

Problems

Links

Last updated: 29.09.2017,
created: 23.09.2017.