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