※この記事では個々のアルゴリズムの実装法とかは扱わないので、知らないアルゴリズムが出てきたらググってください。
0. グラフで解けないか疑う
〇〇は何通りありますか？という類いの問題は、グラフを利用して解けることがあります。（特に二部マッチング）
解放がすぐに思いつかなかったときは「グラフで解けないか考えてみる」といいかもしれません。
1. 最短経路問題
あ、この問題最短経路問題で解けるやんってなるのに労力がかかる問題はABCでは見たことがないのでそのへんの説明は省きますね
最短経路問題でABCで出てくるのは基本的に次の3種類だと思います。
- ダイクストラ/BFS
- ベルマンフォード
- ワーシャルフロイド
順番に見ていきましょう。
a. ダイクストラ/BFS
言わずと知れたアルゴリズムです。最短経路問題の8割ぐらいはダイクストラとかそのレベルだと思います。
BFSの挙動は「ダイクストラの辺の重み全部0バージョン」です。なので（グラフの）BFSで解ける問題はすべてダイクストラでも解けます。
コンテスト中に実装すると結構時間かかるので2次元の文字列で与えられるタイプのBFSと普通のダイクストラぐらいはスニペットで持っておいてもいいかも知れません。ちなみに僕は持ってません。
b. ベルマンフォード法
グラフに負の辺がある場合に使うらしいです。ダイクストラより重いそうです。
負の辺がありえる状況では、しばしば「ぐるぐる回れば回るほどコストが安くなる」みたいな状況が出てきます。大概問題文にその場合何を出力すればいいか書いてあります（書いてなかったらClarを投げましょう）
c. ワーシャルフロイド法
「すべての辺と辺の間の最短経路を知りたい」という状況で使います。実装は信じられないぐらいシンプルで興味深いアルゴリズムですが、O(N^3)なのでクッソ重いです。
2. 最小全域木
クラスカル法で求められます。ちなみにUnion-Findはクラスカル法以外のシチュエーションでも出てくるのでちゃんと理解しましょう。
「つながり」を見たらUnion-Find、ぐらいの考え方で大丈夫だと思います。
3. 彩色数
概念だけさらっておけば大丈夫だと思います。そんな見かけない印象があるんですが僕だけですか？
4. 最大流・最小カット
言わずと知れたアルゴリズムです。実装はACLに丸投げでいいと思います。二部マッチングは最大流で解けます。 マッチング・安定集合・辺カバー・点カバー あたりは二部マッチングだと最大流で解けたりするらしいので、概念だけでもさらっておけばコンテスト中にググれるようになると思います。あと頻出のパターン（燃やす埋める）もさらっとくといいかも知れません。
「よくある変形パターン」は覚えておいたほうがいいと思います。蟻本を読みましょう。
5. 最小費用流
実装はACLに丸投げでいいと思います。 これもよくある変形パターンを覚えておいたほうがいいと思います。蟻本を読みましょう。
6. 2-SAT・SCC
よく知らないのですが、やっといたほうが良さげですね。
7. 同じものをまとめる
入力一つから無数に辺や頂点を作らされてTLEするときはまとめることができないか考えてみるといいかも知れません（グラフで解けないだけなんてこともあると思いますが….）
入力一つから無数に辺や頂点を作らされるタイプは数学的変形が必要なタイプもあるので必ずこう、とは言えない気がしますが…
同じものをまとめるという意味では強連結成分分解が使えるシチュエーションもあるかもしれませんね。
8. 違うものを分ける
拡張ダイクストラ（頂点倍加）などです。基本的な発想としては一つのものに複数のステータスがある場合、それぞれのステータスを別のものとして扱ってしまおう、的な考え方です。
頻出の分け方もいくつかありそうなので、思いつけないなら暗記してしまうのも手かもしれませんね。
9. 更新をサボる
グラフの一部に変更が入った場合に、過去の情報を完全に捨てきらずに更新できる場合があるようです。見かけてからググったんで大丈夫だと思います。
10. 頂点の数が少ない場合
順列全探索・bit全探索・bit DP・半分全列挙・DP あたりの一般に通用するアルゴリズムが持ち出せるかも知れません
（半分全列挙はあんまりない気がしますが）
11. 木
一応ただのグラフだと大概上に書いてあるようなことで解決できると思うんですが、木だと以下のようなテクニックが必要になると思います。
・直径
・BFS
・DFS
・LCA
・DP
12. アルゴリズムは知ってるんだよ！思いつかないんだよ！
これは個人的な意見なんですが、「これはこのアルゴリズムを使うと解けます」って言われたら問題が解けるようになる人はアルゴリズムで全探索すればいいと思います。要するに解法のリストをつくておいて片っ端から順番に試していくってことです。
この記事で書いた解法のリストはこんな感じです。蟻本+典型90問に出てくるものは多分全部のせたはず。
最短経路問題
・ベルマンフォード
・ダイクストラ/BFS
・ワーシャルフロイド
最小全域木
クラスカル
Union-Find
彩色数
最大流・最小カット
・マッチング
・安定集合
・辺カバー
・点カバー
最小費用流
2-SAT
強連結成分分解
同じものをまとめる
・入力一つから無数に辺をつくるのをやめる
違うものを分ける
・拡張ダイクストラ
頂点の数が少ない場合
・順列全探索
・ビット全探索
・bit DP
・半分全列挙
・DP
更新をサボる
木
・直径
・BFS
・DFS
・LCA
・DP
こんな感じだと思います。気が向いたら数え上げバージョンも作りますね。