atcoder.dsu.DSU

class atcoder.dsu.DSU(n: int = 0)

Implement (union by size) + (path halving)

Reference: Zvi Galil and Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems

Methods

__init__(n: int = 0) → None

groups() → List[List[int]]

leader(a: int) → int

merge(a: int, b: int) → int

same(a: int, b: int) → bool

size(a: int) → int