Table of Contents

DisjointSet<T> Class

Definition

Namespace
Bodu.Collections.Generic.Graphs
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
DisjointSet{T}.cs

Provides an element-keyed disjoint-set (union-find) structure that tracks a partition of added elements into disjoint subsets and supports near-constant-time union and connectivity queries.

public sealed class DisjointSet<T> where T : notnull

Type Parameters

T

The type of the elements. Must be non-nullable.

Inheritance
DisjointSet<T>
Inherited Members
Extension Methods

Examples

var groups = new DisjointSet<string>(new[] { "a", "b", "c", "d" });
groups.Union("a", "b");
groups.Union("c", "d");
groups.Union("b", "c");                       // merges both pairs into one set

bool connected = groups.AreConnected("a", "d"); // true
int sets = groups.SetCount;                     // 1

Remarks

Elements are introduced with MakeSet(T) (or its alias Add(T)), each starting in its own singleton set. Union(T, T) merges the subsets containing two elements, and Find(T) returns the canonical representative of an element's subset. Two elements are connected exactly when they share a representative.

The implementation combines path-halving compression with union by size, giving an amortized cost per operation of O(α(n)), where α is the inverse Ackermann function (effectively constant). Element identity is determined by the IEqualityComparer<T> supplied at construction, or Default when none is supplied.

Constructors

DisjointSet()

Initializes a new instance of the DisjointSet<T> class that is empty and uses the default equality comparer.

public DisjointSet()

DisjointSet(IEnumerable<T>, IEqualityComparer<T>?)

Initializes a new instance of the DisjointSet<T> class containing the specified elements, each in its own singleton set.

public DisjointSet(IEnumerable<T> items, IEqualityComparer<T>? comparer = null)

Parameters

items IEnumerable<T>

The elements to add.

comparer IEqualityComparer<T>

The comparer used to determine element identity, or null to use the default comparer.

Exceptions

ArgumentNullException

items is null.

DisjointSet(IEqualityComparer<T>?)

Initializes a new instance of the DisjointSet<T> class that is empty and uses the specified equality comparer.

public DisjointSet(IEqualityComparer<T>? comparer)

Parameters

comparer IEqualityComparer<T>

The comparer used to determine element identity, or null to use the default comparer.

Properties

Comparer

Gets the equality comparer used to determine element identity.

public IEqualityComparer<T> Comparer { get; }

Property Value

IEqualityComparer<T>

The comparer supplied at construction, or Default.

Count

Gets the total number of elements tracked by the structure.

public int Count { get; }

Property Value

int

The number of distinct elements added.

SetCount

Gets the number of disjoint sets currently represented.

public int SetCount { get; }

Property Value

int

The count of distinct subsets.

Methods

Add(T)

Adds the specified element as a new singleton set. This is an alias for MakeSet(T).

public bool Add(T item)

Parameters

item T

The element to add.

Returns

bool

true if the element was added; false if it was already present.

Exceptions

ArgumentNullException

item is null.

AreConnected(T, T)

Determines whether the two specified elements belong to the same subset.

public bool AreConnected(T a, T b)

Parameters

a T

The first element.

b T

The second element.

Returns

bool

true if both elements share a representative; otherwise, false.

Exceptions

ArgumentNullException

Either element is null.

ArgumentException

Either element has not been added to the structure.

Clear()

Removes all elements, returning the structure to an empty state.

public void Clear()

Contains(T)

Determines whether the specified element has been added.

public bool Contains(T item)

Parameters

item T

The element to locate.

Returns

bool

true if the element is present; otherwise, false.

Exceptions

ArgumentNullException

item is null.

Find(T)

Returns the canonical representative of the set containing the specified element.

public T Find(T item)

Parameters

item T

The element whose representative is requested.

Returns

T

The representative element of the subset containing item.

Exceptions

ArgumentNullException

item is null.

ArgumentException

item has not been added to the structure.

MakeSet(T)

Adds the specified element as a new singleton set.

public bool MakeSet(T item)

Parameters

item T

The element to add.

Returns

bool

true if the element was added; false if it was already present.

Exceptions

ArgumentNullException

item is null.

SizeOf(T)

Returns the number of elements in the subset containing the specified element.

public int SizeOf(T item)

Parameters

item T

The element whose subset size is requested.

Returns

int

The number of elements in the subset containing item.

Exceptions

ArgumentNullException

item is null.

ArgumentException

item has not been added to the structure.

TryFind(T, out T)

Attempts to return the canonical representative of the set containing the specified element.

public bool TryFind(T item, out T representative)

Parameters

item T

The element whose representative is requested.

representative T

When this method returns, contains the representative element, if found; otherwise, the default value.

Returns

bool

true if the element was found; otherwise, false.

Exceptions

ArgumentNullException

item is null.

Union(T, T)

Merges the subsets containing the two specified elements.

public bool Union(T a, T b)

Parameters

a T

The first element.

b T

The second element.

Returns

bool

true if the elements were in different subsets and a merge occurred; otherwise, false.

Exceptions

ArgumentNullException

Either element is null.

ArgumentException

Either element has not been added to the structure.

Applies to

ProductVersions
.NET8, 10