Cod sursa(job #2450777)

Utilizator retrogradLucian Bicsi retrograd Data 24 august 2019 16:07:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 1.61 kb
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");
}