Disjoint Sets Data Structure Implementation

Below are implementations in C++ and C# of the Disjoint Sets data structure (also known as the Union-Find data structure). The implementation is fairly simple (about 200 lines with comments).

Overview

The point of the this data structure is to allow efficient grouping of elements. The two main operations that a Disjoint Sets data structure provides are Union (merging two sets) and Find (identifying which set an element belongs to). For this reason, the data stucture is sometimes referred to as Union-Find.

For a more detailed description of the Disjoint Sets data structure, refer to the corresponding wikipedia entry.

C++ and C# Source Code

Here are the files for the C++ implementation:

DisjointSets.h - Header file
DisjointSets.cpp - Implementation file
Sample.cpp - An example program

Here are the files for the C# implementation:

DisjointSets.cs - The DisjointSets class
Sample.cs - An example program

License

All of the source files linked on this web page are released under Emil's give-away license.