verification/library-checker/scc-kosaraju/src/main.rs

• View this file on GitHub
• Last update: 2026-01-01 00:11:18+09:00
• Problem: https://judge.yosupo.jp/problem/scc

Depends on

• Strongly Connected Components (Kosaraju) (graph/strongly-connected-components-kosaraju/src/lib.rs)

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc

use itertools::Itertools;
use proconio::input;

use strongly_connected_components_kosaraju::StronglyConnectedComponents;

fn main() {
    std::thread::Builder::new()
        .stack_size(64 * 1024 * 1024)
        .spawn(actual_main)
        .unwrap()
        .join()
        .unwrap();
}

fn actual_main() {
    input! {
        n: usize,
        m: usize,
        ab: [(usize, usize); m],
    }
    let mut scc = StronglyConnectedComponents::new(n);
    ab.iter().for_each(|&(a, b)| scc.add_edge(a, b));
    let groups = scc.scc();

    println!("{}", groups.len());
    for group in groups {
        println!("{} {}", group.len(), group.iter().join(" "));
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
Rust	example_00	AC	5 ms	2 MB
Rust	large_cycle_00	AC	152 ms	83 MB
Rust	max_random_00	AC	786 ms	77 MB
Rust	max_random_01	AC	804 ms	76 MB
Rust	max_random_02	AC	777 ms	76 MB
Rust	max_random_03	AC	765 ms	76 MB
Rust	max_random_04	AC	756 ms	76 MB
Rust	random_00	AC	638 ms	62 MB
Rust	random_01	AC	709 ms	69 MB
Rust	random_02	AC	82 ms	47 MB
Rust	random_03	AC	573 ms	41 MB
Rust	random_04	AC	386 ms	32 MB

Back to top page