Class QuickFindDisjointSet

An IDisjointSet implementation based on a simple to store set ids of each of the values stored in the Disjoint Set.

Inheritance

System.Object

QuickFindDisjointSet

Implements

IDisjointSet

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures.DisjointSets

Assembly: MoreStructures.dll

Syntax

public class QuickFindDisjointSet : IDisjointSet

Remarks

• This implementation optimizes Find(Int32) and AreConnected(Int32, Int32) runtime, making them constant-time operations, at the cost of Union(Int32, Int32), which requires a full scan of the underlying list and hence is a O(n) operation.
  
• Check QuickUnionDisjointSet for an alternative implementation of IDisjointSet which does the opposite, in terms of optimization.

Constructors

QuickFindDisjointSet(Int32)

Builds a Disjoint Set structure containing valuesCount disjoint values, each one into its own singleton set.

Declaration

public QuickFindDisjointSet(int valuesCount)

Parameters

Type	Name	Description
System.Int32	valuesCount

Remarks

Requires initializing all the valuesCount items of the underlying list.
Time and Space Complexity are O(n).

Properties

SetsCount

Declaration

public int SetsCount { get; }

Property Value

Type	Description
System.Int32

Remarks

Obtained as the number of distinct values in the underlying list, which is scanned linearly.
Time Complexity is O(n) and Space Complexity is O(1), where n is ValuesCount.

ValuesCount

Declaration

public int ValuesCount { get; }

Property Value

Type	Description
System.Int32

Remarks

Set at construction time, based on the constructor parameter.
Time and Space Complexity are O(1).

Methods

AreConnected(Int32, Int32)

Declaration

public bool AreConnected(int first, int second)

Parameters

Type	Name	Description
System.Int32	first
System.Int32	second

Returns

Type	Description
System.Boolean

Remarks

Calculated in constant-time by comparing the set id of the first value with the set id of the second value.
Time and Space Complexity are O(1).

Find(Int32)

Declaration

public int Find(int value)

Parameters

Type	Name	Description
System.Int32	value

Returns

Type	Description
System.Int32

Remarks

Calculated in constant-time by retrieving the set id at index value in the underlying list.

Union(Int32, Int32)

Declaration

public void Union(int first, int second)

Parameters

Type	Name	Description
System.Int32	first
System.Int32	second

Remarks

Retrieves the set id A of first and B of second, via Find(Int32).
Then replaces all occurrences of B with A, in the underlying list.
Time Complexity is O(n) and Space Complexity is O(1).

Implements

IDisjointSet

Extension Methods

SuffixStructureNodeExtensions.GetAllSuffixesFor<TEdge, TNode>(TNode, TextWithTerminator)