verification/aizu-online-judge/grl_3_c_kosaraju/src/main.rs

• View this file on GitHub
• Last update: 2026-01-01 00:11:18+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C

Depends on

• Union Find (data-structure/union-find/src/lib.rs)
• Strongly Connected Components (Kosaraju) (graph/strongly-connected-components-kosaraju/src/lib.rs)

Code

// verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C

use proconio::input;

use strongly_connected_components_kosaraju::StronglyConnectedComponents;
use union_find::UnionFind;

fn main() {
    input! {
        v: usize,
        e: usize,
        st: [(usize, usize); e],
        q: usize,
        uv: [(usize, usize); q],
    }
    let mut scc = StronglyConnectedComponents::new(v);
    st.iter().for_each(|&(s, t)| scc.add_edge(s, t));
    let groups = scc.scc();

    let mut uf = UnionFind::new(v);
    for group in groups {
        for i in 0..group.len() {
            uf.merge(group[0], group[i]);
        }
    }

    for &(u, v) in &uv {
        println!("{}", if uf.same(u, v) { 1 } else { 0 });
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
Rust	00_sample_00.in	AC	4 ms	2 MB
Rust	01_small_00.in	AC	3 ms	2 MB
Rust	01_small_01.in	AC	3 ms	2 MB
Rust	01_small_02.in	AC	3 ms	2 MB
Rust	01_small_03.in	AC	3 ms	2 MB
Rust	02_medium_00.in	AC	3 ms	2 MB
Rust	02_medium_01.in	AC	3 ms	2 MB
Rust	03_sparse_00.in	AC	3 ms	2 MB
Rust	03_sparse_01.in	AC	3 ms	2 MB
Rust	03_sparse_02.in	AC	3 ms	2 MB
Rust	03_sparse_03.in	AC	4 ms	2 MB
Rust	04_dense_00.in	AC	3 ms	2 MB
Rust	04_dense_01.in	AC	3 ms	2 MB
Rust	04_dense_02.in	AC	4 ms	2 MB
Rust	04_dense_03.in	AC	6 ms	2 MB
Rust	05_rand_00.in	AC	7 ms	2 MB
Rust	05_rand_01.in	AC	7 ms	2 MB
Rust	05_rand_02.in	AC	10 ms	3 MB
Rust	06_linear_00.in	AC	37 ms	5 MB
Rust	06_linear_01.in	AC	37 ms	5 MB
Rust	07_linear_00.in	AC	40 ms	6 MB
Rust	07_linear_01.in	AC	39 ms	6 MB
Rust	08_grid_00.in	AC	45 ms	5 MB
Rust	08_grid_01.in	AC	68 ms	6 MB

Back to top page