AtCoder Beginner Contest 285 D

https://atcoder.jp/contests/abc285/tasks/abc285_d

(S, T)をエッジとしてグラフにします。それがループを含まないか調べます。少し前に連結成分に分けるコードを書いたので、連結成分に分けて、それぞれの成分が木になっているかを調べます。

// Change Usernames
#![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(|(_, vs)| vs.len()).sum::<usize>() / 2
    }
    
    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 ////////////////////

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

fn make_graph(edges: Vec<(String, String)>) -> Graph {
    let vs = edges.iter().
                map(|(v1, v2)| vec![v1.to_string(), v2.to_string()]).
                flatten().collect::<HashSet<String>>();
    let dic = vs.into_iter().enumerate().map(|(i, key)| (key, i)).
                                collect::<HashMap<String, usize>>();
    let mut g = HashMap::<usize, Vec<usize>>::new();
    for (v1, v2) in edges.iter() {
        let i1 = dic.get(v1).unwrap();
        let i2 = dic.get(v2).unwrap();
        let e1 = g.entry(*i1).or_insert(vec![]);
        (*e1).push(*i2);
        let e2 = g.entry(*i2).or_insert(vec![]);
        (*e2).push(*i1);
    }
    Graph { g }
}

fn f(edges: Vec<(String, String)>) -> bool {
    let graph = make_graph(edges);
    let subgraphs = graph.divide_into_connected();
    subgraphs.iter().all(|g| g.num_nodes() == g.num_edges() + 1)
}

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