ARC039 D. 旅行会社高橋君

その他

問題

N頂点、M辺からなる無向グラフが与えられる。(多重辺や自己ループはなし)
Q個の「同じ辺を通らず、頂点aから頂点bを通って頂点cに行くことができるか？」のクエリがくるので、それに答える。


N<=10^5
M<=20^5
Q<=10^5
各クエリのa,b,cは互いに異なる

考え方

行くことができないケースを考える。

a-x-c
  |
  b

上記のような場合、bに行って戻るために2回辺を通らないといけない。


グラフ理論では、上記のような辺を「橋」といい、橋を含まない連結な無向グラフを「二重辺連結成分」という。
上記の問題は、二重辺連結成分に分割し、橋でそれらを連結したグラフを考えると、木になるので、木において、aからcのパスにbがあるかどうかの判定になる。


木においてaからcのパスにbがあるかどうかの判定は、a〜bの距離とb〜cの距離の和がa〜cの距離と一致するかで判断でき、木の距離はlcaを使って高速に求めることができる。


二重辺連結成分は橋を除いたグラフでUnionFindで頂点をまとめあげれば作成できる。
橋を除いたグラフは、橋をみつけることができれば作成できる。


橋は、根を適当に決めて、dfsで辿って、すでにたどった点に戻る辺を見つけ、その辺の両端をつなぐ別のルートはこの辺がある限り橋にはなり得ないので、全部の辺をたどってそうならなかった辺が橋となる。
これは愚直にやるとO(NM)程度かかってしまうが、imos法で上記のような辺の両端で+1,-1とし、葉ノード側から累積していけばO(N+M)で求められる。


また、全体的にメモリを無駄遣いしやすくMLEしてしまうので、節約(使い終わったらfree)する。