Disjoint Set

0.9.0 verified Mon Apr 27 auth: no python

A Python implementation of the disjoint set (union-find) data structure, featuring path compression and union by rank/size. Current version 0.9.0, requires Python >=3.10. The library is stable with occasional updates.

pip install disjoint-set

Common errors

error ImportError: cannot import name 'DisjointSet' from 'disjoint_set' ↓

cause Incorrect import path or library not installed.

fix

Install using 'pip install disjoint-set' and import as 'from disjoint_set import DisjointSet'.

error TypeError: DisjointSet() takes no arguments ↓

cause Trying to pass initial elements to the constructor, which is not supported.

fix

Instantiate without arguments: ds = DisjointSet(); then add elements via find/union.

error AttributeError: 'DisjointSet' object has no attribute 'add' ↓

cause Attempting to use a non-existent method 'add'. This library does not have an explicit add method.

fix

Use 'find' to implicitly add an element: ds.find(x).

Warnings

gotcha The library does not support initializing with a set of elements; elements are added implicitly on find/union. If you need to pre-populate, call find on each element first. ↓

fix Explicitly call 'ds.find(x)' for each element before unions, or use 'ds.add(x)' if available (not in this library).

gotcha The library uses path compression and union by size, but the implementation may not guarantee O(alpha(n)) amortized if used incorrectly. Ensure you always call union with two elements (creates if missing). ↓

fix Always call find after union to compress paths immediately for subsequent operations.

Imports

DisjointSet
```
from disjoint_set import DisjointSet
```

Quickstart

Quickstart: create a DisjointSet, use union and find.

from disjoint_set import DisjointSet

ds = DisjointSet()
ds.find(1)  # returns 1
ds.union(1, 2)
ds.find(2)  # returns 1 (or 2, depending on implementation)
print(ds.connected(1, 2))  # True
print(len(ds))  # 1 (number of disjoint sets)