アルゴリズムと数学 043

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_am

連結成分に分けるコードとだいたい同じです。
グラフの隣接ノードを追加するのに、get_mutを使うと便利ですね。

// Depth First Search
#![allow(non_snake_case)]

use std::collections::{HashSet, HashMap};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

struct Graph {
    g: HashMap<usize, Vec<usize>>
}

impl Graph {
    fn num_nodes(&self) -> usize {
        self.g.len()
    }
    
    fn num_edges(&self) -> usize {
        self.g.iter().map(|(_, vs)| vs.len()).sum::<usize>() / 2
    }
    
    fn is_connected(&self) -> bool {
        let mut unvisited = self.g.keys().map(|v| *v).
                                    collect::<HashSet<usize>>();
        let v0 = unvisited.iter().next().unwrap();
        let mut g = HashMap::<usize, Vec<usize>>::new();
        let mut stack: Vec<usize> = vec![*v0];
        while !stack.is_empty() {
            let v = stack.pop().unwrap();
            let vs = self.g.get(&v).unwrap();
            let vs_copy = vs.iter().map(|v1| *v1).
                                    collect::<Vec<usize>>();
            g.insert(v, vs_copy);
            unvisited.remove(&v);
            for v1 in vs.iter() {
                if unvisited.contains(v1) {
                    stack.push(*v1);
                    unvisited.remove(v1);
                }
            }
        }
        unvisited.is_empty()
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<(usize, usize)>) {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    let edges: Vec<(usize, usize)> = (0..M).map(|_| read_vec::<usize>()).
                                            map(|v| (v[0]-1, v[1]-1)).collect();
    (N, edges)
}

fn create_graph(N: usize, edges: Vec<(usize, usize)>) -> Graph {
    let mut g: HashMap<usize, Vec<usize>> = (0..N).map(|v| (v, vec![])).collect();
    for (v, w) in edges.into_iter() {
        let nodes1 = g.get_mut(&v).unwrap();
        nodes1.push(w);
        let nodes2 = g.get_mut(&w).unwrap();
        nodes2.push(v)
    }
    Graph { g }
}

fn f(N: usize, edges: Vec<(usize, usize)>) -> bool {
    let graph = create_graph(N, edges);
    graph.is_connected()
}

fn main() {
    let (N, edges) = read_input();
    if f(N, edges) {
        println!("The graph is connected.")
    }
    else {
        println!("The graph is not connected.")
    }
}