Mega Man SpeedRun

解説

各ステージ間の関係をグラフ化して考えてみましょう。ステージ $i$ を攻略するとステージ $W_i$ が簡単になる、という条件を $i \rightarrow W_i$ の有向辺として有向グラフの問題に帰着させます。 この問題で与えられるグラフはどんな形をしているのでしょうか？何個か実際にグラフを作って試してみると、このグラフは必ず各連結成分ごとに閉路をもつことが分かります。具体的には、各連結成分ごとに以下の二つのどちらかの構造を取ります。

• サイクルグラフ(閉路)だけからなる構造 ... A
• サイクルグラフ(閉路)と、そのいづれかの頂点に向かうような有向辺からなる構造 ... B

それぞれの構造について、答えを考えます。

• Aの場合

閉路内のどのステージ(頂点)を選んでも、選んだステージ以外のステージは有向辺を順に辿っていくことで簡単になります。

よって、閉路内のどのステージ(頂点)の難易度を $d_1,d_2,...,d_k$ としたとき、答えは $min(d_1,d_2,...,d_k)$ となります。

• Bの場合

　閉路に向かうような有向辺からなる構造において、このグラフは必ず入次数 $0$ の頂点(ステージ)を持ちます。 これらのステージは他のどのステージを攻略しても簡単になることがないため、通常の状態で攻略する必要があります。

一方、それ以外のステージは入次数 $0$ の頂点(ステージ)から有向辺を辿るようにして攻略していくことで必ず簡単になります。

よって、入次数 $0$ の頂点(ステージ)の難易度を $d_1,d_2,...,d_l$ としたとき、答えは $\displaystyle \sum_{i=1}^{l}d_i$ となります。

問題の答えは各連結成分における答えの値の和です。これは入次数 $0$ の頂点からdfsまたはbfsを行い(Bの構造を全探索)、さらにdfsまたはbfsで通らなかった頂点についてdfsまたはbfsを行う(Aの構造を全探索)ことで $O(N)$ で求めることができます。

追記

この問題で与えられるような $N$ 頂点 $N$ 辺グラフを、Functional Graph(有向なもりグラフ) と呼びます。