examples/library_checker_unionfind.rs

• View this file on GitHub
• Last update: 2024-04-26 00:41:30+09:00
• Problem: https://judge.yosupo.jp/problem/unionfind

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
• Union Find（素集合データ構造） (src/data_structure/union_find.rs)
• src/lib.rs
• src/math.rs
• src/math/binomial.rs
• src/utils.rs
• src/utils/binary_search.rs
• src/utils/compression.rs

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/unionfind

use proconio::input;
use rust_procon_lib::data_structure::union_find::union_find::UnionFind;

fn main() {
    input! {
        n: usize,
        q: usize,
    }

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

    for _ in 0..q {
        input! {
            t: usize,
            u: usize,
            v: usize,
        }

        match t {
            0 => {
                uf.unite(u, v);
            }
            1 => {
                println!("{}", if uf.is_same(u, v) { 1 } else { 0 });
            }
            _ => unreachable!(),
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
Rust	example_00	AC	5 ms	2 MB
Rust	path_00	AC	105 ms	8 MB
Rust	path_01	AC	89 ms	8 MB
Rust	path_02	AC	22 ms	8 MB
Rust	path_03	AC	22 ms	8 MB
Rust	random_00	AC	129 ms	6 MB
Rust	random_01	AC	118 ms	7 MB
Rust	random_02	AC	73 ms	4 MB
Rust	random_03	AC	21 ms	5 MB
Rust	random_04	AC	88 ms	3 MB
Rust	random_05	AC	83 ms	5 MB
Rust	random_06	AC	67 ms	7 MB
Rust	random_07	AC	12 ms	4 MB
Rust	random_08	AC	31 ms	3 MB
Rust	random_09	AC	116 ms	6 MB

Back to top page