Disjoint Set
Overview
Uses disjoint set. Used implementation has recursive find,
which kind of sucks but I couldn’t find any repo-available
implementation with iterative find.
Therefore I created a new pull request to fix that.
Complexity
| Time | Space (iterative find) | |
|---|---|---|
constructor |
O(n) |
O(n) |
connect, query |
in practice* O(1) amortized |
O(1) |
* real amortized complexity is O(α(n)) where α(n) is inverse Ackermann function.