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