Cod sursa(job #2450773)

Utilizator retrogradLucian Bicsi retrograd Data 24 august 2019 16:02:46
Problema Parcurgere DFS - componente conexe Scor 0
Compilator rs Status done
Runda Arhiva educationala Marime 1.66 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(str::split_ascii_whitespace);
        Scanner(Box::new(iter))
    }
    fn next<T: std::str::FromStr>(&mut self) -> Option<T>
    where
        T::Err: std::fmt::Debug,
    {
        self.0
            .next()
            .map(|x: &'a str| x.parse().expect("Parse error"))
    }
}

struct Graph(Vec<Vec<usize>>);
impl Graph {
    fn read(scanner: &mut Scanner) -> Graph {
        let n: usize = scanner.next().unwrap();
        let m: usize = scanner.next().unwrap();
        let mut graph = Graph(vec![Vec::new(); n]);
        for _ in 0..m {
            let a: usize = scanner.next().unwrap();
            let b: usize = scanner.next().unwrap();
            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");
}