ステージの関係をグラフで表す. 各ステージをグラフの頂点とする.

ステージ \(i\) について, ステージ \(j\) を先にクリアすることでステージ \(i\) の難易度が半分になるとき, グラフの頂点 \(j\) から頂点 \(i\) に辺を作成することとする.

頂点は連結成分ごとに考えればいいので, まずは Union-Find を使って頂点を連結成分に分解する.

次に問題の形式から各頂点の次数は高々 1 であるので, グラフにある閉路の数は高々 \(1\) であり, その閉路を1つの頂点 \(r\) とみなすと連結成分の残りの頂点は \(r\) を根とする木構造となる. よって, 閉路中の1つの頂点のみが通常の難易度でクリアしなければならず, 連結成分の残りの頂点は半分の難易度でクリアできる. このとき, 閉路中の頂点のうち難易度が最も低い頂点を通常の難易度でクリアすれば難易度の合計は一番小さくなる.

閉路抽出および根の特定のためのトポロジカルソートには強連結成分分解を使う.