AtCoder Beginner Contest 292 D

https://atcoder.jp/contests/abc292/tasks/abc292_d

グラフを連結成分に分解します。
このときグラフをHashMap>で表すと、Vecの要素数がエッジの数の2倍になるのですが、自分へのエッジは二重に数えていないので、その分をカウントしないといけません。

// Unicyclic Components
#![allow(non_snake_case)]

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


//////////////////// 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()
}

fn YesNo(b: bool) -> String {
    return if b { "Yes".to_string() } else { "No".to_string() }
}

//////////////////// 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(|(&v, vs)|
                vs.iter().map(|&w| if w == v { 2 } else { 1 }).sum::<usize>()
                        ).sum::<usize>() / 2
    }
    
    fn is_isolated(&self, v: usize) -> bool {
        !self.g.contains_key(&v)
    }
    
    fn divide_into_connected(&self) -> Vec<Graph> {
        let mut subgraphs = Vec::<Graph>::new();
        let mut unvisited = self.g.keys().map(|v| *v).
                                    collect::<HashSet<usize>>();
        while !unvisited.is_empty() {
            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);
                    }
                }
            }
            subgraphs.push(Graph { g })
        }
        subgraphs
    }
    
    fn create_from_edges(edges: Vec<(usize, usize)>) -> Graph {
        let mut g = HashMap::<usize, Vec<usize>>::new();
        for (u, v) in edges.into_iter() {
            let e1 = g.entry(u).or_insert(vec![]);
            (*e1).push(v);
            if u != v {
                let e2 = g.entry(v).or_insert(vec![]);
                (*e2).push(u);
            }
        }
        Graph { g }
    }
}


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

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

fn f(N: usize, graph: Graph) -> bool {
    if (0..N).any(|v| graph.is_isolated(v)) {
        return false
    }
    
    let subgraphs = graph.divide_into_connected();
    subgraphs.into_iter().all(|g| g.num_nodes() == g.num_edges())
}

fn main() {
    let (N, graph) = read_input();
    println!("{}", YesNo(f(N, graph)))
}