Skip to main content

library_checker/graph/
two_edge_connected_components.rs

1use competitive::prelude::*;
2use competitive::{
3    data_structure::UnionFind,
4    graph::{LowLink, UndirectedSparseGraph},
5};
6
7#[verify::library_checker("two_edge_connected_components")]
8pub fn two_edge_connected_components(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, m, edges: [(usize, usize); m]);
11    let graph = UndirectedSparseGraph::from_edges(n, edges);
12    let low_link = LowLink::new(&graph);
13    let mut uf = UnionFind::new(n);
14    for &(mut u, mut v) in &graph.edges {
15        if low_link.ord[u] > low_link.ord[v] {
16            std::mem::swap(&mut u, &mut v);
17        }
18        if low_link.ord[u] >= low_link.low[v] {
19            uf.unite(u, v);
20        }
21    }
22    let groups = uf.all_group_members();
23    pp!(groups.len());
24    for group in groups.into_values() {
25        pp!(group.len(), @it group);
26    }
27}