Project Nayuki

Disjoint-set data structure


The disjoint-set data structure, also known as union-find, is useful for quickly testing whether nodes in a graph are connected or not. The code provided here implements union-by-rank, path compression, and size queries. My high-quality implementations are open-source and are available in a number of programming languages.


Here is the API documentation of the Java version of the library: (other languages are largely similar)

Source code

  • Data structure library
  • JUnit test suite
  • An easier-to-understand version of DisjointSet for educational purposes. Less efficient because it creates a node object per element, instead of using flat arrays of integers. But it has the same asymptotic time complexity as the streamlined version. This is not the same as NaiveDisjointSet, which has much worse asymptotic time complexity (but is easy to verify for correctness).

License: MIT (open source)