Struct UnionFind 

pub struct UnionFind { /* private fields */ }

0..n の要素を互いに素な集合へ分割して管理します。

経路圧縮とサイズによる併合を使用します。各操作の償却計算量は O(α(N)) です。 添字は 0-indexed で、範囲外の添字を渡すと panic します。

Examples

use atcoder::data_structure::union_find::UnionFind;

let mut dsu = UnionFind::new(4);
assert!(dsu.merge(0, 1));
assert!(dsu.same(0, 1));
assert_eq!(dsu.size(0), 2);
assert_eq!(dsu.group_count(), 3);

Implementations

impl UnionFind

pub fn new(n: usize) -> Self

0..n の各要素を含む単一要素集合を作ります。計算量・メモリ量は O(N) です。

pub fn find(&mut self, x: usize) -> usize

x の属する集合の代表元を返します。経路圧縮を行い、償却計算量は O(α(N)) です。 x >= n なら panic します。

pub fn merge(&mut self, x: usize, y: usize) -> bool

x と y の集合を併合します。

新しく併合した場合は true、既に同じ集合なら false を返します。 償却計算量は O(α(N)) です。x >= n または y >= n なら panic します。

pub fn same(&mut self, x: usize, y: usize) -> bool

x と y が同じ集合なら true を返します。代表元の検索を行うため、 償却計算量は O(α(N)) です。x >= n または y >= n なら panic します。

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

x の属する集合の要素数を返します。代表元の検索を行うため、 償却計算量は O(α(N)) です。x >= n なら panic します。

pub const fn group_count(&self) -> usize

現在の集合数を返します。計算量は O(1) です。

Trait Implementations

impl Clone for UnionFind

fn clone(&self) -> UnionFind

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for UnionFind

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.