Disjoint Set Union

Source code: src/pydsadoc/_tree/dsu.py

class UnionFind(num_vert: int, /, *args, **kwargs)

Implementation of the DSU with a sequential list.

It’s notably that the amortized time complexity of DSU is \(O(\alpha(n))\).

__str__() → str

Implement built-in function print().

find(x: int, /) → int

The find operation with path compression.

The worst-case time complexity is \(O(\log n)\).

union(x: int, y: int, /) → None

The union operation by rank.

The worst-case time complexity is \(O(\log n)\).

The Amortized Time

In this case, The Inverse Ackermann Function \(\alpha(n)\) is in fact treated as a constant. So the amortized time complexity of the two operations of the UnionFind can be optimized to \(O(1)\).