Module c

ABC 404 C - Cycle Graph?

refs: https://atcoder.jp/contests/abc404/tasks/abc404_c

サイクルグラフとなる条件はおそらく次の通り.

• 各頂点の次数が 2 (入次 1, 出次 1)であること
• 辺の数が頂点数と等しいこと
• グラフが連結であること

数の検証は単純に実行でき, 連結かどうかは任意頂点からすべての頂点に到達できることを検証すればよい.

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

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        vec: [(usize, usize); m],
    }

    if n != m {
        println!("No");
        return;
    }

    let edge_map = make_edge_map(&vec);

    if !is_two_dist(&edge_map) {
        println!("No");
        return;
    }

    if is_connected(n, &edge_map) {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn make_edge_map(vec: &[(usize, usize)]) -> HashMap<usize, Vec<usize>> {
    let mut edge_map = HashMap::<usize, Vec<usize>>::new();
    for (a, b) in vec {
        edge_map.entry(*a).or_default().push(*b);
        edge_map.entry(*b).or_default().push(*a);
    }
    edge_map
}

fn is_two_dist(edge_map: &HashMap<usize, Vec<usize>>) -> bool {
    edge_map.values().all(|edges| edges.len() == 2)
}

fn is_connected(n: usize, edge_map: &HashMap<usize, Vec<usize>>) -> bool {
    let mut visited = HashSet::new();
    let first_node = 1;

    dfs(first_node, edge_map, &mut visited);

    visited.len() == n
}

fn dfs(node: usize, edge_map: &HashMap<usize, Vec<usize>>, visited: &mut HashSet<usize>) {
    if visited.contains(&node) {
        return;
    }
    visited.insert(node);

    for &next_node in &edge_map[&node] {
        if !visited.contains(&next_node) {
            dfs(next_node, edge_map, visited);
        }
    }
}