Cod sursa(job #3233491)

Utilizator susdomesticussusdomesticus susdomesticus Data 3 iunie 2024 17:19:50
Problema Componente biconexe Scor 90
Compilator rs Status done
Runda Arhiva educationala Marime 2.92 kb
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);
}