AtcoderのABCレベルのグラフ問題について調べることがあったのでまとめます。
ABCで出るグラフ問題
ABCの問題をざっと見ていったところ、以下のような問題が多いです。
最短経路問題
重みを持つ辺が出てきて、点に向かう最小コストを探索します。
基本的にはダイクストラ法で解けて、たまにベルマンフォード法が必要になります。
単一始点最短経路問題に帰着することで時間内に解けるような問題が頻繁に出るので、出来ると良いかもしれません。
以下典型っぽい問題です。
ダイクストラで単一始点最短経路問題に帰着します。
ダイクストラでも解けますし、ワーシャるフロイドを使っても解けます。最小コストだけでなく経路を使う問題です。
ベルマンフォードを使う問題です。
深さ優先探索、幅優先探索する問題
与えられたグラフを深さ優先探索や幅優先探索で探索する問題です。
組み合わせなど外の分野の問題と複合的に出ることも多いです。
以下典型っぽい問題です。
実態は木構造です。TreeDPと言われる解放を取ります。
接続性を探索で調べます。
グラフ問題は難しい問題も多いですが、マラソンや現実の問題にも応用しやすいので基礎は抑えておいて損はなさそうですね！