nekolib/ds/
union_find.rs

1//! union-find。
2
3use super::super::traits::disjoint_set;
4
5use std::cell::RefCell;
6
7use disjoint_set::DisjointSet;
8
9#[derive(Clone, Copy)]
10enum Item {
11    Parent(usize),
12    Size(usize),
13}
14
15/// union-find。
16///
17/// # Complexity
18/// |演算|時間計算量|
19/// |---|---|
20/// |`new`|$\\Theta(n)$|
21/// |`unite`|amortized $O(\\alpha(n))$|
22/// |`repr`|amortized $O(\\alpha(n))$|
23/// |`equiv`|amortized $O(\\alpha(n))$|
24/// |`count`|amortized $O(\\alpha(n))$|
25/// |`subset`|$\\Theta(n)$|
26///
27/// より tight には、$n$ 要素 $m$ クエリのとき、$O(m\\cdot\\alpha(m, n)+n)$ 時間となる。
28/// ただし、$\\alpha(m, n)$ は次のように定義される。
29/// $$ \\alpha(m, n) = \\min\\{k\\in\\mathbb{N}\\mid J\_k(\\lfloor\\log\_2(n)\\rfloor)\\le 1+m/n\\}. $$
30/// ここで、$g^\\diamond = (\\lceil{\\log\_2}\\rceil\\circ g)^\\star$ とし、$J\_0(r) =
31/// \\lceil(r-1)/2\\rceil$, $J\_k(r)=J\_{k-1}^\\diamond(r)$ ($k\\gt 0$) である。
32/// より直感的には、${\\underbrace{J\_0^{\\diamond\\diamond\\cdots\\diamond}}\_{k\\text{ many }\\diamond{\\text{s}}}}(\\lfloor\\log\_2(n)\\rfloor)$ が $1+m/n$ 以下になる最小の $k$ が $\\alpha(m, n)$ である。
33///
34///
35/// ## Complexity analysis
36///
37/// 参考文献ふたつめの PDF の概略を書く。`todo!()`
38///
39/// これらより、$f(m, n, r)\\le (\\alpha(m, n)+2)\\cdot m+2n$ が言える。
40///
41/// Note: $\\alpha\'(m, n) = \\min\\{k\\in\\mathbb{N}\\mid \\alpha\_k(n)\\le 3\\}$ として
42/// $\\alpha(m, n) = O(\\alpha\'(m, n))$ である。
43///
44///
45/// # Examples
46/// ```
47/// use nekolib::traits::DisjointSet;
48/// use nekolib::ds::UnionFind;
49///
50/// let mut uf = UnionFind::new(4);
51/// assert!(!uf.equiv(0, 2));
52/// uf.unite(0, 1);
53/// uf.unite(1, 2);
54/// assert!(uf.equiv(0, 2));
55/// assert!(!uf.equiv(0, 3));
56/// assert_eq!(uf.count(0), 3);
57/// ```
58///
59/// # References
60/// - <http://www.gabrielnivasch.org/fun/inverse-ackermann>
61/// - <http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf>
62#[derive(Clone)]
63pub struct UnionFind {
64    n: usize,
65    buf: RefCell<Vec<Item>>,
66}
67
68impl DisjointSet for UnionFind {
69    fn new(n: usize) -> Self {
70        Self { n, buf: RefCell::new(vec![Item::Size(1); n]) }
71    }
72    fn len(&self) -> usize { self.n }
73    fn unite(&mut self, u: usize, v: usize) -> bool {
74        let u = self.repr(u);
75        let v = self.repr(v);
76        if u == v {
77            return false;
78        }
79        let mut buf = self.buf.borrow_mut();
80        let (su, sv) = (buf[u], buf[v]);
81        match (su, sv) {
82            (Item::Size(su), Item::Size(sv)) => {
83                let (child, par) = if su < sv { (u, v) } else { (v, u) };
84                buf[par] = Item::Size(su + sv);
85                buf[child] = Item::Parent(par);
86            }
87            _ => unreachable!(),
88        }
89        true
90    }
91    fn repr(&self, mut u: usize) -> usize {
92        let mut res = u;
93        let mut buf = self.buf.borrow_mut();
94        while let Item::Parent(v) = buf[res] {
95            res = v;
96        }
97        let mut bu = buf[u];
98        while let Item::Parent(pu) = bu {
99            let tmp = pu;
100            buf[u] = Item::Parent(res);
101            u = tmp;
102            bu = buf[u];
103        }
104        res
105    }
106    fn count(&self, u: usize) -> usize {
107        let u = self.repr(u);
108        if let Item::Size(res) = self.buf.borrow()[u] {
109            res
110        } else {
111            unreachable!()
112        }
113    }
114}
115
116#[test]
117fn test() {
118    let n = 4;
119    let mut uf = UnionFind::new(n);
120    assert!(!uf.equiv(1, 3));
121    assert_eq!(uf.count(1), 1);
122    assert_eq!(uf.count(3), 1);
123    uf.unite(1, 3);
124    assert!(uf.equiv(1, 3));
125    assert_eq!(uf.count(1), 2);
126    assert_eq!(uf.count(3), 2);
127    uf.unite(2, 3);
128    assert!(uf.equiv(2, 3));
129    assert!(uf.equiv(1, 2));
130    assert!(!uf.equiv(1, 0));
131}
nekolib/ds/union_find.rs

nekolib/ds/
union_find.rs
