難しい問題にも既知のパターンが隠れていますが、手がかりはサイズよりも構造にあります。辺の重みが異なる正の値ならダイクストラ法、重みが等しければBFS、重みが0と1だけなら両端キューを使った0-1 BFSです。前提条件があり「それを守る順序」が求められているなら、トポロジカルソートです。接続が追加されるだけで、「今つながっているか?」を問われるなら、ユニオンファインドです。
重なり合う選択にわたって方法の数を数える、または最良の合計を求めるなら動的計画法です:まず状態を定義し、次に遷移を定義します。範囲の問い合わせの合間に値が変わるなら、合計にはフェニック木、最小値や最大値など引き算で元に戻せないものにはセグメント木を使います。
各問題について、パターンを決める手がかりと、最も近い別の選択肢を除外する手がかりを挙げてください。面接官が聞きたいのは、その2文目です。