pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 10 E. Pursuit For Artifacts

codeforces.com

問題概要

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

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

解法

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

  • a-b パス上の連結成分の中に artifact を含むものがあれば YES
  • a-b パス上の連結成分を繋ぐ辺の中に artifact を含むものがあれば YES

になる。

二重辺連結成分内では 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 というトレイルになる。

f:id:pekempey:20160327235533p:plain:w400

Educational Codeforces Round 10 E. Pursuit For Art ...

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