verification/library-checker/scc-tarjan/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 (Tarjan) (graph/strongly-connected-components-tarjan/src/lib.rs)

Code

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

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

use strongly_connected_components_tarjan::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	125 ms	74 MB
Rust	max_random_00	AC	715 ms	65 MB
Rust	max_random_01	AC	731 ms	64 MB
Rust	max_random_02	AC	727 ms	65 MB
Rust	max_random_03	AC	738 ms	64 MB
Rust	max_random_04	AC	735 ms	64 MB
Rust	random_00	AC	575 ms	53 MB
Rust	random_01	AC	669 ms	59 MB
Rust	random_02	AC	68 ms	30 MB
Rust	random_03	AC	563 ms	40 MB
Rust	random_04	AC	386 ms	30 MB

Back to top page