Struct UnionFind

Source

pub struct UnionFind { /* private fields */ }

Expand description

Union Find はグラフの連結成分を管理します。

Implementations§

Source §

impl UnionFind

Source

pub fn new(n: usize) -> Self

頂点数を n として初期化します。

Source

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

頂点 i の属する連結成分の代表元を返します。

§Examples

use union_find::UnionFind;
let mut uf = UnionFind::new(6);
uf.unite(0, 1);
uf.unite(1, 2);
uf.unite(3, 4);

// [(0, 1, 2), (3, 4), (5)]
assert_eq!(uf.find(0), uf.find(0));
assert_eq!(uf.find(0), uf.find(1));
assert_eq!(uf.find(1), uf.find(2));
assert_eq!(uf.find(0), uf.find(2));
assert_eq!(uf.find(3), uf.find(4));

assert_ne!(uf.find(0), uf.find(3));
assert_ne!(uf.find(0), uf.find(5));

Source

pub fn unite(&mut self, i: usize, j: usize) -> Option<UniteResult>

頂点 i の属する連結成分と頂点 j の属する連結成分をつなげます。

もともと i と j が同じ連結成分だった場合は None を返します。

§Examples

use union_find::UnionFind;
let mut uf = UnionFind::new(6);
assert!(uf.unite(0, 1).is_some());
assert!(uf.unite(1, 2).is_some());
assert!(uf.unite(3, 4).is_some());

// [(0, 1, 2), (3, 4), (5)]
assert!(uf.unite(0, 2).is_none());
assert!(uf.unite(3, 3).is_none());

assert!(uf.unite(4, 5).is_some());

Source

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

頂点 i の属する連結成分のサイズ (頂点数) を返します。

§Examples

use union_find::UnionFind;
let mut uf = UnionFind::new(6);
uf.unite(0, 1);
uf.unite(1, 2);
uf.unite(3, 4);

// [(0, 1, 2), (3, 4), (5)]
assert_eq!(uf.size(0), 3);
assert_eq!(uf.size(1), 3);
assert_eq!(uf.size(2), 3);
assert_eq!(uf.size(3), 2);
assert_eq!(uf.size(4), 2);
assert_eq!(uf.size(5), 1);

Source

pub fn same(&mut self, i: usize, j: usize) -> bool

頂点 i と頂点 j が同じ連結成分に属するかどうかを返します。

§Examples

use union_find::UnionFind;
let mut uf = UnionFind::new(6);
assert!(uf.same(0, 0));
assert!(uf.same(3, 3));
assert!(uf.same(5, 5));

uf.unite(0, 1);
uf.unite(1, 2);
uf.unite(3, 4);

// [(0, 1, 2), (3, 4), (5)]
assert!(uf.same(0, 1));
assert!(uf.same(1, 2));
assert!(uf.same(0, 2));
assert!(uf.same(3, 4));

Source

pub fn count_groups(&self) -> usize

連結成分数を返します。

§Examples

use union_find::UnionFind;
let mut uf = UnionFind::new(6);
uf.unite(0, 1);
uf.unite(1, 2);
uf.unite(3, 4);

// [(0, 1, 2), (3, 4), (5)]
assert_eq!(uf.count_groups(), 3);