AtCoder Beginner Contest 293 D

https://atcoder.jp/contests/abc293/tasks/abc293_d

グラフを作って隣接ノードが2つずつあればループになっています。
ただ、問題なのはノードが2つの連結成分です。1と2を連結すると、

{1: [2], 2: [1]}

となりますが、反対側を結んだ時に強引に、

{1: [2, 2], 2: [1, 1]}

と隣接ノードを加えるとうまくいきます。

// Tying Rope
#![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 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
    }
}


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

type Connection = (usize, char, usize, char);

fn read_connection() -> Connection {
    let v: Vec<String> = read_vec();
    let A: usize = v[0].parse().ok().unwrap();
    let B: char = v[1].chars().next().unwrap();
    let C: usize = v[2].parse().ok().unwrap();
    let D: char = v[3].chars().next().unwrap();
    (A-1, B, C-1, D)
}

fn read_graph() -> Graph {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    let mut g: HashMap<usize, Vec<usize>> = (0..N).map(|i| (i, vec![])).
                                                                collect();
    for _ in 0..M {
        let (A, _, C, _) = read_connection();
        let e1 = g.entry(A).or_insert(vec![]);
        (*e1).push(C);
        let e1 = g.entry(C).or_insert(vec![]);
        (*e1).push(A);
    }
    Graph { g }
}

fn is_loop(graph: &Graph) -> bool {
    graph.g.iter().all(|(_, v)| v.len() == 2)
}

fn f(graph: Graph) -> (usize, usize) {
    let subgraphs = graph.divide_into_connected();
    let num_loops = subgraphs.iter().filter(|g| is_loop(g)).count();
    let num_not_loops = subgraphs.len() - num_loops;
    (num_loops, num_not_loops)
}

fn main() {
    let graph = read_graph();
    let (a, b) = f(graph);
    println!("{} {}", a, b)
}