PAST #11 : 第11回 アルゴリズム実技検定 過去問の G を解いた。
- G - 木の判定
https://atcoder.jp/contests/past202206-open/tasks/past202206_g
- 提出: https://atcoder.jp/contests/past202206-open/submissions/38507785
- N 頂点 N - 1 辺が木であるためには連結であれば良い
- ac-library の Dsu (Union-Find) を使う手もあるが、 BFS で頂点 1 から到達可能な頂点を調べてすべての頂点に到達したかを調べた
use std::collections::VecDeque; use proconio::{input, marker::Usize1}; fn main() { input! { n: usize, ab: [(Usize1, Usize1); n - 1], }; let mut edges = vec![vec![]; n]; for (a, b) in ab.iter().copied() { edges[a].push(b); edges[b].push(a); } let mut visited = vec![false; n]; let mut deque = VecDeque::new(); visited[0] = true; deque.push_back(0); while let Some(u) = deque.pop_front() { for v in edges[u].iter().copied() { if visited[v] { continue; } visited[v] = true; deque.push_back(v); } } let ans = visited.into_iter().all(|b| b); println!("{}", if ans { "Yes" } else { "No" }); }
今日のコミット。
- rust-atcoder 1 commit
- rust-sandbox 1 commit