DisjointSet

master

A Swift implementation of a disjoint-set data structure.
fumoboy007/DisjointSet

DisjointSet

A Swift implementation of a disjoint-set data structure.

Overview of Disjoint-Set

A disjoint-set is like a regular set but with an extra superpower: it can partition members into disjoint subsets without increasing the upper bound time complexity of standard operations.

Algorithmic Time Complexity

Operation Time Complexity
isEmpty O(1)
count O(1)
insert(_:unioningWith:) O(1)
contains(_:) O(1)
count(ofSubsetsContaining:) O(1)
allSubsets() O(n)
subset(containing:) O(n)

To confirm that the real-world results match the theory, use DisjointSet.attabench.

API Usage

See Tests/DisjointSetTests/LeetCodeTests.swift.

Compatibility

Tested using Swift 4. MIT license.

Description

  • Swift Tools 4.2.0
View More Packages from this Author

Dependencies

  • None
Last updated: Mon Aug 15 2022 18:57:55 GMT-0500 (GMT-05:00)