アルゴリズムと数学 047

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

グラフをたどるだけですね。

// Bipartite Graph
#![allow(non_snake_case)]

use std::collections::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 ////////////////////

type Node = usize;
type Edge = (Node, Node);

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

impl Graph {
    fn create_from_edges(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<usize>> = (0..N).map(|_| vec![]).collect();
        for (v, w) in edges.into_iter() {
            g[v].push(w);
            g[w].push(v)
        }
        Graph { g }
    }
}


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

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

fn f(N: usize, edges: Vec<Edge>) -> bool {
    let graph = Graph::create_from_edges(N, edges);
    let mut colors: Vec<i32> = (0..N).map(|_| 0).collect();
    let mut unvisited: HashSet<Node> = (0..N).collect();
    
    while !unvisited.is_empty() {
        let v0 = unvisited.iter().next().unwrap();
        let mut stack: Vec<usize> = vec![*v0];
        while !stack.is_empty() {
            let v = stack.pop().unwrap();
            unvisited.remove(&v);
            for w in graph.g[v].iter() {
                if colors[*w] == 0 {
                    colors[*w] = if colors[v] == 1 { 2 } else { 1 };
                    stack.push(*w)
                }
                else if colors[*w] == colors[v] {
                    return false
                }
            }
        }
    }
    true
}

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