7K12 blog

猫でも分かるアルゴリズム解説

2020-06-13から1日間の記事一覧

AOJ 1160 島はいくつある?

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4416724 互いに行き来できる=頂点の到達可能性=BFSかDFSで到達した頂点に印を付ける 互いに行き来できるということは、グリッドをグラフに変換したときに閉路が存在するということなので強連結成分分…

AOJ ALDS1_11_B 深さ優先探索

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4573439 問題設定が長いので見落としがないよう注意 最短距離(最短到達時間)で更新するとき、更新済み頂点を continue するのを忘れずに書く DFSの基本問題。DFSで木構造の各頂点を処理する時は①か…