目录
- DisjointSet.attabenchAdded `DisjointSet.count(ofSubsetsContaining:)` and fixed `LeetCodeTests.testFindRedundantConnection()`6年前
- SourcesAdded `DisjointSet.count(ofSubsetsContaining:)` and fixed `LeetCodeTests.testFindRedundantConnection()`6年前
- TestsRemoved reference to `DisjointSetPerformanceTests`, which no longer exists6年前
- .gitignoreAdded `DisjointSet.attabench` to measure real-world time complexity6年前
- LICENSE.mdImplemented `DisjointSet` and associated tests6年前
- Package.swiftImplemented `DisjointSet` and associated tests6年前
- README.mdAdded `DisjointSet.count(ofSubsetsContaining:)` and fixed `LeetCodeTests.testFindRedundantConnection()`6年前
邀请码
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
isEmptyO(1)countO(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.