グラフ理論
atcoder.jp kenkoooo.comのdifficulty同じ数値でも最近の問題と昔の問題で難易度に差があるように感じるんだけど、こんなもんなんですかね 初手の方針 まだ知識がないので少ない中で知っている知識に帰着させようとしてUnionFindで実装しようとした。 が、繋…
atcoder.jp 初手の方針 隣接リストを作ってdfsでカウントするような方針。 グループに属する人数を求めると計算量は(n^ 2)かな? 今回はnが10^ 5なので間に合わず後述するUnion-Findというデータ構造で工夫する必要がある。 Submission #10513724 - AtCoder …
atcoder.jp 初手の方針 蟻本のDFS/BFSで迷路探索問題は見ていてアルゴリズムはわかっていたが実装力が足りなくて手が出せなかった。 幅優先探索について 幅優先探索の実装において抑えておくポイントみたいなものを記しておく。 以下のような迷路を例にとっ…