Cod sursa(job #2751137)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 14 mai 2021 12:45:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 1.26 kb
use std::fs::File;
use std::io::{*};

fn dfs( node : usize, graph : &Vec<Vec<usize>>, visited : &mut Vec<bool> ) {
    if visited[node] == true { return; }
    visited[node] = true;

    for neighbour in &graph[node] {
        dfs(*neighbour, graph, visited);
    }
}

fn main() {
    let mut input = BufReader::new(File::open("dfs.in").unwrap());
    let mut output = BufWriter::new(File::create("dfs.out").unwrap());

    let mut line = String::new();
    input.read_line(&mut line).unwrap();
    let vars : Vec<usize> = line.split(" ").map(|x| x.trim().parse().unwrap()).collect();
    let n : usize = vars[0];
    let m : usize = vars[1];

    let mut graph : Vec<Vec<usize>> = vec![vec![]; n + 1];

    for _i in 0..m {
        let mut line = String::new();
        input.read_line(&mut line).unwrap();
        let vars : Vec<usize> = line.split(" ").map(|x| x.trim().parse().unwrap()).collect();

        let x = vars[0];
        let y = vars[1];

        graph[x].push(y);
        graph[y].push(x);
    }

    let mut visited : Vec<bool> = vec![false; n + 1];

    let mut nr_conex = 0;
    for i in 1..n+1 {
        if visited[i] == false {
            nr_conex = nr_conex + 1;
        }

        dfs(i, &graph, &mut visited);
    }

    writeln!(output, "{}", nr_conex).unwrap();
}