LeetCode グラフ問題：prefix_max / suffix_min で連結成分を O(N) に

要約

LeetCode の Daily Problem で、前向き・後ろ向きジャンプができるグラフの連結成分を求める問題。BFS の O(N³) から始まり、グラフが無向・連結成分が連続区間であるという構造を利用して prefix_max / suffix_min による O(N) 解法にたどり着く思考プロセスが参考になる。

思考プロセス（問題のモデル化）

1. 素朴解（O(N³)）: 各インデックスから BFS でグラフ探索
2. 無向グラフに気づく: j→i の後ろ向きジャンプ可 ↔ i→j の前向きジャンプ可 → 無向グラフ
3. 連結成分の構造: nums[i] と nums[j] が同成分なら間の全要素も同成分 → 成分は常に連続区間
4. 境界条件: インデックス k に境界がある ↔ 区間をまたぐエッジが存在しない ↔ prefix_max[k] <= suffix_min[k+1]
5. O(N) 解法: 配列を走査し prefix_max[k] <= suffix_min[k+1] の時点で成分境界を確定

ポイント

• Union-Find でも解けるが、区間構造を使う方がシンプル
• 問題の構造（グラフの特性）を先に見抜くことでアルゴリズムが自然に決まる
• prefix_max / suffix_min は「境界検出」のための自然なツール