nekolib/traits/
disjoint_set.rs

1//! 素集合に関するトレイトです。
2
3/// 共通要素を持たない集合族で、併合が可能なもの。
4pub trait DisjointSet {
5    /// 集合族を $\\{\\{0\\}, \\{1\\}, \\dots, \\{n-1\\}\\}$ で初期化する。
6    fn new(n: usize) -> Self;
7    /// 集合族全体に含まれる要素数 $n$ を返す。
8    fn len(&self) -> usize;
9    /// 集合族が空であれば `true` を返す。
10    fn is_empty(&self) -> bool { self.len() == 0 }
11    /// $u$ を含む集合と $v$ を含む集合を併合する。
12    /// 集合族に変化があれば `true` を返す。
13    /// $u$ と $v$ が元々同じ集合に含まれていれば `false` を返す。
14    fn unite(&mut self, u: usize, v: usize) -> bool;
15    /// $u$ を含む集合の代表元を返す。
16    fn repr(&self, u: usize) -> usize;
17    /// $u$ を含む集合の要素数を返す。
18    fn count(&self, u: usize) -> usize;
19    /// $u$ と $v$ が同じ集合に含まれていれば `true` を返す。
20    fn equiv(&self, u: usize, v: usize) -> bool { self.repr(u) == self.repr(v) }
21    /// $u$ を含む集合の要素を列挙する。
22    fn subset(&self, u: usize) -> Vec<usize> {
23        (0..self.len()).filter(|&v| self.equiv(u, v)).collect()
24    }
25    /// 分割を返す。
26    ///
27    /// $u$ が代表元のとき、$u$ 番目の `Vec` にそれと等価な要素たちが入る。
28    fn partition(&self) -> Vec<Vec<usize>> {
29        let mut res = vec![vec![]; self.len()];
30        for i in 0..self.len() {
31            res[self.repr(i)].push(i);
32        }
33        res
34    }
35}
nekolib/traits/disjoint_set.rs

nekolib/traits/
disjoint_set.rs
