Struct DisjointSetUnionRollback

pub struct DisjointSetUnionRollback { /* private fields */ }

UnionFind 経路圧縮を行わないことで undo を可能にする

Implementations

impl DisjointSetUnionRollback

pub fn new(n: usize) -> DisjointSetUnionRollback

要素数 n の dsu を構築する

pub fn root(&self, target: usize) -> usize

根を取得 経路圧縮を行わない

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

対象の木をマージ 経路圧縮を行わないため変更されるノード数は高々2 変更箇所をスタックで保存

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

同じ木に存在するか

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

所属する木のサイズ

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

所属する木のランク

pub fn undo(&mut self)

unite 操作の undo

pub fn snapshot(&mut self)

現時点の状態を保存 復元には rollback_snapshot

pub fn get_history_length(&self) -> usize

現時点での保存されている操作回数を返す

pub fn rollback_snapshot(&mut self)

rollback_snapshot で保存された状態へ復元

pub fn rollback(&mut self, n: usize)

復元 任意のタイミングで get_history_length を実行し取得した 値を使用する

pub fn get_same_group(&mut self, x: usize) -> HashSet<usize>

同じ木に含まれるノードを返す

pub fn get_all_groups(&mut self) -> HashMap<usize, HashSet<usize>>

全ノードを返却

Trait Implementations

impl Clone for DisjointSetUnionRollback

fn clone(&self) -> DisjointSetUnionRollback

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for DisjointSetUnionRollback

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

Formats the value using the given formatter.