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

Java (SE 5+)
  • 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 the NaiveDisjointSet within DisjointSetTest, which has much worse asymptotic time complexity (but is easy to verify for correctness).
  • DisjointSet.ts: Data structure library
    The public API is identical to the hand-written JavaScript version.
  • Reuse the test infrastructure from the JavaScript version
Python (compatible with 2 and 3)
C++ (C++11 and above)
C (C99 and above)

License: MIT (open source)