Educational Codeforces Round 10 E. Pursuit For Artifacts

グラフが与えられる。グラフの辺には artifact があるかどうかの情報が込められている。

artifact を持つ辺を使って頂点 a から頂点 b に行くようなトレイルはあるだろうか。

グラフを二重辺連結成分で潰したあとグラフにおいて、

になる。

二重辺連結成分内では s から t へ任意の辺を使って行くことが可能であるという事実に基づく。

使いたい辺を e=(u,v) としたとき、s→u→v→t あるいは s→v→u→t というトレイルが存在することを示す。

二重辺連結成分内の任意の 2 点 s, t を通るサーキットが存在することは容易にわかる。

仮想頂点 x と y を次図のように作る。このグラフもまた二重辺連結になるので、x と y を通るサーキットが存在する。

そのサーキットは x→s→u→y→v→t→x あるいは x→s→v→y→u→t→x である。u→y→v の部分を u→v に短絡させれば s→u→v→t というトレイルになる。

二重辺連結成分分解を使った問題はまだ解いたことがなかったので丁度良かった。