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)$ である。

$1$ つ目のテストケースのみ考える。

入力を受け取る。

n: 6
m: 7
edges:
(1, 5)
(1, 3)
(3, 5)
(2, 5)
(3, 4)
(3, 6)
(4, 6)

頂点 $1$ を根として、入力順の隣接リストで深さ優先探索する。

最初に頂点 $1$ の値を $0$ とする。
頂点 $1$ から頂点 $5$ へ進むので、頂点 $5$ の値を $1$ とする。

頂点 $5$ から未訪問の頂点 $3$ へ進み、値を $2$ とする。
頂点 $3$ から頂点 $4$ へ進み、値を $3$ とする。
頂点 $4$ から頂点 $6$ へ進み、値を $4$ とする。

頂点 $6$ から先には未訪問の頂点がないので戻る。
その後、頂点 $5$ から未訪問の頂点 $2$ へ進み、値を $2$ とする。

したがって、各頂点の値は次のようになる。

a: {0, 2, 2, 3, 1, 4}

例えば頂点 $3$ の値は $2$ である。
隣接する頂点 $1,5,4,6$ の値はそれぞれ $0,1,3,4$ なので、値が $1$ 小さい頂点は頂点 $5$ だけである。

他の頂点についても同様に条件を満たすため、この列を出力できる。

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

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

特になし。