Struct Dsu

pub struct Dsu { /* private fields */ }

A Disjoint set union (DSU) with union by size and path compression.

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

In the following documentation, let $n$ be the size of the DSU.

Example

use ac_library::Dsu;
use proconio::{input, source::once::OnceSource};

input! {
    from OnceSource::from(
        "5\n\
         3\n\
         0 1\n\
         2 3\n\
         3 4\n",
    ),
    n: usize,
    abs: [(usize, usize)],
}

let mut dsu = Dsu::new(n);
for (a, b) in abs {
    dsu.merge(a, b);
}

assert!(dsu.same(0, 1));
assert!(!dsu.same(1, 2));
assert!(dsu.same(2, 4));

assert_eq!(
    dsu.groups()
        .into_iter()
        .map(|mut group| {
            group.sort_unstable();
            group
        })
        .collect::<Vec<_>>(),
    [&[0, 1][..], &[2, 3, 4][..]],
);

Implementations

impl Dsu

pub fn new(size: usize) -> Self

Creates a new Dsu.

Constraints

• $0 \leq n \leq 10^8$

Complexity

• $O(n)$

pub fn merge(&mut self, a: usize, b: usize) -> usize

Performs the Uɴɪᴏɴ operation.

Constraints

• $0 \leq a < n$
• $0 \leq b < n$

Panics

Panics if the above constraints are not satisfied.

Complexity

• $O(\alpha(n))$ amortized

pub fn same(&mut self, a: usize, b: usize) -> bool

Returns whether the vertices $a$ and $b$ are in the same connected component.

Constraints

• $0 \leq a < n$
• $0 \leq b < n$

Panics

Panics if the above constraint is not satisfied.

Complexity

• $O(\alpha(n))$ amortized

pub fn leader(&mut self, a: usize) -> usize

Performs the Fɪɴᴅ operation.

Constraints

• $0 \leq a < n$

Panics

Panics if the above constraint is not satisfied.

Complexity

• $O(\alpha(n))$ amortized

pub fn size(&mut self, a: usize) -> usize

Returns the size of the connected component that contains the vertex $a$.

Constraints

• $0 \leq a < n$

Panics

Panics if the above constraint is not satisfied.

Complexity

• $O(\alpha(n))$ amortized

pub fn groups(&mut self) -> Vec<Vec<usize>>

Divides the graph into connected components.

The result may not be ordered.

Complexity

• $O(n)$