ARC224 C - Ascending Labels

昇順ラベル

考え方

小さい数が大量にあると、隣接の中に $1$ 小さい値が複数あって条件に反する危険が大きい。
ということで、頂点 $1$ の値を $0$ を決めた後で、以下をループして貪欲に埋めていけばよい。

さて、これで、どの頂点も隣接に自身より $1$ 小さい値が少なくとも $1$ つ存在することは保証される。
あとは、それが $2$ つ以上になることがないことを示せばよい。

仮に、頂点 $X$ の隣接である $Y,Z$ が $1$ 小さい値をもつという状態が発生したとしよう。

この $3$ つの中で、最後に追加したのが $X$ であることはありえない。
なぜなら、$Y$ と $Z$ の片方が決まった段階で $X$ が選択肢に入ってくるから。
$X$ を $Y$ の値より $1$ 大きい値に決める選択肢にあるのに、先に $Z$ が $Y$ と同じ値に決まることはない。

しかし、最後に追加したのが $Y$ であることもありえない。
なぜなら、$Y$ は $X$ に隣接しているので、$Y$ が $X$ より $1$ 小さい値に決まることはありえない。
$Z$ についても同様。

したがって、そのような状態が発生すると、決定順位に必ず矛盾が発生する。
すなわち、そのような状況は絶対に発生しない。

ということで、冒頭に述べた貪欲法で構成していけばよい。
そして、実のところ、これはただの深さ優先探索であり、計算量は $O\left(\sum (N+M)\right)$ である。

ただの深さ優先探索なので省略。

再帰による深さ優先探索では、言語によっては再帰が深くなりすぎてエラーする場合がある。
その場合は、stack を用いる方の実装にする必要がある。

C++では、この程度では何も問題ないようである。

特になし。