use std::{
cmp::min,
fs::File,
io::{BufRead, BufReader, BufWriter, Write},
};
type Graph = Vec<Vec<usize>>;
fn read() -> (
usize,
Graph,
Vec<(usize, usize)>,
Vec<usize>,
Vec<usize>,
Vec<Vec<usize>>,
) {
let input_file = File::open("biconex.in").unwrap();
let buffered_reader = BufReader::new(input_file);
fn parse_line(line: &str) -> (usize, usize) {
let splits: Vec<&str> = line.split_whitespace().collect();
assert_eq!(splits.len(), 2);
return (
splits[0].parse::<usize>().unwrap(),
splits[1].parse::<usize>().unwrap(),
);
}
let mut it = buffered_reader.lines();
let (n, m) = parse_line(&it.next().unwrap().unwrap());
let mut graph = vec![Vec::new(); n + 1];
for _ in 1..=m {
let (x, y) = parse_line(&it.next().unwrap().unwrap());
graph[x].push(y);
graph[y].push(x);
}
(
n,
graph,
Vec::new(),
vec![0; n + 1],
vec![0; n + 1],
Vec::new(),
)
}
fn dfs(
graph: &Graph,
node: usize,
prev_node: usize,
edges: &mut Vec<(usize, usize)>,
step: &mut Vec<usize>,
lowest: &mut Vec<usize>,
components: &mut Vec<Vec<usize>>,
) {
lowest[node] = step[node];
for next_node in &graph[node] {
if *next_node == prev_node {
continue;
}
if lowest[*next_node] != 0 {
lowest[node] = min(lowest[node], lowest[*next_node]);
continue;
}
step[*next_node] = step[node] + 1;
edges.push((node, *next_node));
dfs(graph, *next_node, node, edges, step, lowest, components);
lowest[node] = min(lowest[node], lowest[*next_node]);
if lowest[*next_node] >= step[node] {
let mut component = Vec::new();
loop {
let (x, y) = edges.pop().unwrap();
component.push(y);
if x == node && y == *next_node {
component.push(node);
break;
}
}
components.push(component);
}
}
}
fn write(components: &Vec<Vec<usize>>) {
let output_file = File::create("biconex.out").unwrap();
let mut buffered_writer = BufWriter::new(output_file);
writeln!(buffered_writer, "{}", components.len()).unwrap();
for component in components {
for node in component {
write!(buffered_writer, "{} ", node).unwrap();
}
writeln!(buffered_writer).unwrap();
}
}
fn main() {
let (n, graph, mut edges, mut step, mut lowest, mut components) = read();
for node in 1..=n {
if step[node] == 0 {
step[node] = 1;
dfs(
&graph,
node,
0,
&mut edges,
&mut step,
&mut lowest,
&mut components,
);
}
}
write(&components);
}