Swift Package Index


A Swift implementation of a disjoint-set data structure.


  • The latest stable release is 1.0.0. Released almost 2 years ago.
  • The last commit to master was almost 2 years ago.

Swift Version Compatibility

  • 1.0.0 and master
    5.3
    5.2
    5.1
    5.0
    4.2
Full build results

Platform Compatibility

  • 1.0.0 and master
    iOS
    macOS(Intel)
    macOS(ARM)
    Linux
    tvOS
    watchOS
Full build results

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.