Yukicoder No.1436 Rgaph
問題の概要
自己ループと二重辺を含まない 頂点
辺の有向グラフが与えられる。各辺に +1 または -1 という値を割り当てて、「任意の 2 頂点
に対して、
から
までのパスで辺の値の合計が０になるものが存在する」ようにせよ。そのような +1 と -1 の割り当てが不可能な場合は -1 を出力せよ。
制約
解法
条件を満たすような +1 と -1 の割り当てが可能であるためには、以下の(A)(B)の両方を満たすことが必要です。
(A) 強連結
(B) 奇数長の初等的サイクルが存在して、かつ、そのサイクルに含まれない辺が1本以上ある
（※初等的サイクルとは、始終点が一致していて、それ以外に同じ頂点が存在しないようなパスのこと）
＜理由＞
(A)は、任意の2点 に対して
から
までのパスが存在するため。
(B)は、もし奇数長のサイクルが存在しないと仮定すると、ある点Sを固定したとき、Sから各点へのパスの長さの偶奇が固定されてしまい（二部グラフ）、Sから奇数距離の点までのパスは +1 と -1 を同じ個数にできなくなるため。奇数長サイクルがある場合、そこから奇数長の初等的サイクルが存在することも言える。また奇数長の初等的サイクルがあったとしてもそれ以外に辺が一本もなければ、一周すると値の合計が正の数または負の数になるので、例えば一周が正の数だった場合には +1 を割り当てた辺の始点から終点まで、合計値０で移動することができない。
実は、上記(A)(B)の両方を満たしていれば、条件を満たすような +1 と -1 の割り当てを構成できます。
具体的には、例えば以下のようにします。
(B)を満たす奇数長サイクル を１つ固定し、その長さを
とする。
上の頂点のうち入次数が 2 以上のものを点
とする（そのような点が必ず存在する）。
からサイクル
をたどって一周するとき、最初の
個の辺を -1、それ以外の辺を +1 とする。
に属さない辺は全て -1 とする。
このようにしておくと
を一周したときの辺の値の合計が+1。
上を
から
以外の点まで移動したときの辺の合計値は必ず０以下。
になっています。
これが正しい割り当てになっていることの説明：
Pを終点とするような に属さない辺に着目すると、
上の点
から点
までの、
に属さない辺のみからなるパスが存在することがわかりますが、
この点
が点
と異なる場合でも、同じ場合でも、一周の値が 1 のループ
の他に、一周の値が負のループが存在することがわかるので、題意を満たします。
というわけで、解答する上では、強連結であるかどうかのチェックの他、「奇数長のサイクルを探す」ことができればよいことになります。
どうやればよいか迷ったのですが、各点からBFSしてループを検出する方針をとりつつ、頂点を倍加する形にしました。（ある頂点について、始点から偶数回でたどり着く場合と、奇数回でたどり着く場合を区別する）
