2022-02-18 アルゴリズムと数学 演習問題集 045, 046, 047 を解いた
アルゴリズムと数学 演習問題集 045 - Easy Graph Problem（★2） を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_bz
自身より頂点番号の小さい隣接頂点が 1 つだけの頂点の数を求める。
頂点ごとに隣接頂点を調べて自身の頂点番号よりも小さいものの数を数える。最後にそれが 1 のものを数える。素朴にやると頂点ごとの隣接頂点を得るために辺を隣接リスト表現に変換して……となりそうだけど辺のリストを走査して大きい側の頂点の個数をインクリメントするだけで同じことができる。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29395314
アルゴリズムと数学 演習問題集 046 - 幅優先探索 を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/abc007_3
問題文の通りに実装すれば良い。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29395774
アルゴリズムと数学 演習問題集 047 - Bipartite Graph を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ao
グラフが二部グラフかを判定する。連結成分ごとに、ある頂点から辺をたどりながら 2 色で交互に塗って矛盾なければ二部グラフになる……はず。
ぼくの場合の実装の概要を書いておく。すべての頂点を未彩色 (2) で初期化する。すべての頂点を走査する。ある頂点が未彩色ならその頂点を 0 で彩色してそこから BFS する。頂点ごとに 0, 1 の 2 色で交互に塗る。既に塗られている場合は塗る予定のものと矛盾しないかを確認する。矛盾しているなら No を出力して終了する。すべての頂点の彩色を終えることができれば Yes を出力する。頂点・辺にはたかだか数回ずつしかアクセスしないので間に合う。
問題文を読んだ時点では連結でないときの扱いが分からなかったのだけど入力例 1 が連結でないときは連結成分ごとに判定だと分かるようになっていたので助かった。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29404826
昨日のことだけど鍋・バススポンジ・キッチンスポンジを買った。
キッチンスポンジはまた何か書くかもしれない。
今日のコミット。