Union Find（素集合データ構造） (src/data_structure/union_find.rs)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-26 00:41:30+09:00
• Link: https://atcoder.jp/contests/practice2/tasks/practice2_a

union_find

UnionFind

無向グラフの連結成分を管理するデータ構造．

new

fn new(n: usize) -> Self

• $n$ 頂点 $0$ 辺の無向グラフを作成する．

  制約

• $n\geq 0$

計算量

• $O(n)$

unite

fn unite(&mut self, mut u: usize, mut v: usize)

• 頂点 $u, v$ の間に辺を追加する．

制約

• $0\leq u, v < n$

計算量

• ならし $O(\alpha(n))$

is_same

fn is_same(&mut self, u: usize, v: usize) -> bool

• 頂点 $u, v$ が同じ連結成分に属するかどうかを返す．

制約

• $0\leq u, v < n$

計算量

• ならし $O(\alpha(n))$

find

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

• 頂点 $v$ が属する連結成分の代表元を返す．

制約

• $0\leq v < n$

計算量

• ならし $O(\alpha(n))$

get_size

fn get_size(&mut self, v: usize) -> usize

• 頂点 $v$ が属する連結成分の頂点数を返す．

制約

• $0\leq v < n$

計算量

• ならし $O(\alpha(n))$

Depends on

• src/data_structure.rs
• src/data_structure/prefix_sum.rs
• src/data_structure/range_set.rs
• セグメント木 (src/data_structure/segment_tree.rs)
• src/data_structure/sorted_set.rs
• src/lib.rs
• src/math.rs
• src/math/binomial.rs
• src/utils.rs
• src/utils/binary_search.rs
• src/utils/compression.rs

Required by

• src/data_structure.rs
• src/data_structure/prefix_sum.rs
• src/data_structure/range_set.rs
• セグメント木 (src/data_structure/segment_tree.rs)
• src/data_structure/sorted_set.rs
• src/lib.rs
• src/math.rs
• src/math/binomial.rs
• src/utils.rs
• src/utils/binary_search.rs
• src/utils/compression.rs

Verified with

• examples/aizu_online_judge_lower_bound.rs
• examples/aizu_online_judge_range_minimum_query.rs
• examples/library_checker_binomial_coefficient_prime_mod.rs
• examples/library_checker_point_add_range_sum.rs
• examples/library_checker_static_range_sum.rs
• examples/library_checker_unionfind.rs

Code

pub mod union_find {
    pub struct UnionFind {
        parent: Vec<usize>,
        size: Vec<usize>,
    }

    #[allow(dead_code)]
    impl UnionFind {
        pub fn new(n: usize) -> Self {
            //! Constructs a union-find tree of size `n`.

            let mut parent = vec![0; n];
            for i in 0..n {
                parent[i] = i;
            }

            Self {
                parent,
                size: vec![1; n],
            }
        }

        pub fn find(&mut self, v: usize) -> usize {
            //! Returns a root of node `v`.

            if self.parent[v] == v {
                v
            } else {
                self.parent[v] = self.find(self.parent[v]);
                self.parent[v]
            }
        }

        pub fn unite(&mut self, mut u: usize, mut v: usize) {
            //! Unites nodes `u` and `v`.

            u = self.find(u);
            v = self.find(v);

            if u == v {
                return;
            }

            if self.size[u] < self.size[v] {
                (u, v) = (v, u);
            }

            self.size[u] += self.size[v];
            self.parent[v] = u;
        }

        pub fn is_same(&mut self, u: usize, v: usize) -> bool {
            //! Returns if nodes `u` and `v` are in the same connected component.

            self.find(u) == self.find(v)
        }

        pub fn get_size(&mut self, v: usize) -> usize {
            //! Returns a size of a connected component where the node `v` belongs.
            let u = self.find(v);

            self.size[u]
        }
    }
}

#[cfg(test)]
mod test {
    use super::union_find::UnionFind;

    #[test]
    fn test_simple() {
        //! borrowed from: https://atcoder.jp/contests/practice2/tasks/practice2_a

        let mut uf = UnionFind::new(4);

        assert_eq!(uf.is_same(0, 1), false);
        uf.unite(0, 1);
        uf.unite(2, 3);
        assert_eq!(uf.is_same(0, 1), true);
        assert_eq!(uf.is_same(1, 2), false);
        uf.unite(0, 2);
        assert_eq!(uf.is_same(1, 3), true);
    }

    #[test]
    fn test_group_size() {
        let mut uf = UnionFind::new(5);

        assert_eq!(uf.get_size(2), 1);
        uf.unite(0, 2);
        uf.unite(2, 3);
        assert_eq!(uf.get_size(2), 3);
        assert_eq!(uf.get_size(1), 1);
    }
}

Back to top page