haar_lib/ds/
persistent_unionfind.rs

1//! 永続UnionFind
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/persistent_unionfind>
5
6use crate::ds::persistent_array::PersistentArray;
7
8/// 永続UnionFind
9#[derive(Clone)]
10pub struct PersistentUnionFind {
11    par: PersistentArray<isize>,
12}
13
14impl PersistentUnionFind {
15    /// 大きさ`n`の[`PersistentUnionFind`]を返す。
16    pub fn new(n: usize) -> Self {
17        Self {
18            par: PersistentArray::new(n, -1),
19        }
20    }
21
22    /// `i`の属する集合の根を返す。
23    pub fn root_of(&self, i: usize) -> usize {
24        let p = self.par[i];
25        if p < 0 {
26            i
27        } else {
28            self.root_of(p as usize)
29        }
30    }
31
32    /// `i`の属する集合の大きさを返す。
33    pub fn size_of(&self, i: usize) -> usize {
34        (-self.par[self.root_of(i)]) as usize
35    }
36
37    /// `i`と`j`が同じ集合にぞくするならば、`true`を返す。
38    pub fn is_same(&self, i: usize, j: usize) -> bool {
39        self.root_of(i) == self.root_of(j)
40    }
41
42    /// `i`の属する集合と`j`の属する集合を統合する。
43    pub fn merge(&self, i: usize, j: usize) -> Self {
44        let i = self.root_of(i);
45        let j = self.root_of(j);
46
47        if i == j {
48            return self.clone();
49        }
50
51        let size_i = self.size_of(i);
52        let size_j = self.size_of(j);
53
54        let mut par = self.par.clone();
55
56        if size_i > size_j {
57            par = par.set(i, -((size_i + size_j) as isize));
58            par = par.set(j, i as isize);
59        } else {
60            par = par.set(j, -((size_i + size_j) as isize));
61            par = par.set(i, j as isize);
62        }
63
64        Self { par }
65    }
66}
haar_lib/ds/persistent_unionfind.rs

haar_lib/ds/
persistent_unionfind.rs
