Pagini recente » Cod sursa (job #1392816) | Cod sursa (job #3185759) | Cod sursa (job #740551) | Cod sursa (job #1830613) | Cod sursa (job #2450777)
struct Scanner<'a>(Box<Iterator<Item = &'a str> + 'a>);
impl<'a> Scanner<'a> {
fn new(string: &'a str) -> Scanner<'a> {
let iter = string.lines().flat_map(|x| x.split(' '));
Scanner(Box::new(iter))
}
fn next<T: std::str::FromStr>(&mut self) -> T {
match self.0.next().expect("Not enough input").parse() {
Ok(res) => res,
Err(_) => panic!("Parse error"),
}
}
}
struct Graph(Vec<Vec<usize>>);
impl Graph {
fn read(scanner: &mut Scanner) -> Graph {
let n: usize = scanner.next();
let m: usize = scanner.next();
let mut graph = Graph(vec![Vec::new(); n]);
for _ in 0..m {
let a: usize = scanner.next();
let b: usize = scanner.next();
graph.0[a - 1].push(b - 1);
graph.0[b - 1].push(a - 1);
}
graph
}
fn dfs(&self, u: usize, vis: &mut Vec<bool>) -> usize {
match vis[u] {
true => 0,
false => {
vis[u] = true;
let sum: usize = self.0[u].iter().map(|v| self.dfs(*v, vis)).sum();
sum + 1
}
}
}
fn solve(&self) -> usize {
let n = self.0.len();
let mut vis = vec![false; n];
(0..n)
.map(|u| self.dfs(u, &mut vis))
.filter(|&x| x > 0)
.count()
}
}
fn main() {
let input = std::fs::read_to_string("dfs.in").expect("Read error");
let mut scanner = Scanner::new(&input);
let graph = Graph::read(&mut scanner);
std::fs::write("dfs.out", format!("{}", graph.solve())).expect("Write error");
}