購入者向け51 / 67 ページ

グラフ（応用）木の直径, 強連結成分, 関節点 & 橋

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Count Subtrees With Max Distance Between Cities	★★★★	高	木の直径
Longest Cycle in a Graph	★★★★	高	強連結成分
Critical Connections in a Network	★★★★	中	関節点 & 橋

応用編では基礎編のダイクストラやトポロジカルソートと同程度の難易度の内容を扱います。グラフ自体が難しい分野であるため、より一層基礎編をしっかりと復習してから応用編にのぞみましょう。基礎編だけでも6, 7割の面接に対応できるくらいの力はつきます。

また本章では、グラフの中でも有名だが解き方を知らないと難しい問題を紹介します。ある意味知識問題として位置付けられますが、ただ解き方を暗記するのではなく、なぜそうなるかを理解して応用できるようにしましょう。

木の直径とは、その木の中で最も長い経路（パス）を指します。（最も遠い2つのノード間の距離です。）既に二分木（基礎）BFS, DFS - 例題2. Diameter（直径）で（重み無し）二分木での木の直径の求め方を一度解いています。今回は一般的な木での直径を求めます。

難易度: ★★★ 重要度: 中

非表示コンテンツ 📝 18,286文字 🖼 14枚の画像

続きは購入後に閲覧できます。