Pagini recente » Cod sursa (job #1595404) | Cod sursa (job #717855) | Cod sursa (job #2127349) | Cod sursa (job #22207) | Cod sursa (job #2751137)
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();
}