@hackage / disjoint-set

Persistent disjoint-sets, a.k.a union-find.

Latest0.2

About

Metadata

  • Last updated , by MaxwellSayles
  • License BSD-3-Clause

  • Maintained by: <maxwellsayles@gmail.com>, <myles.maxfield@gmail.com>

  • Lottery factor: 0

Links

Installation

Readme

This is a persistent data structure for disjoint sets.

The algorithm is described in "Introduction to Algorithms" by Cormen, et al. The implementation here uses both union by rank and path compression. We incur an O(logn) overhead because of the use of persistent maps.

Data.IntDisjointSet is as strict as possible.