CodeFes2017予選B C問題めも

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder

昨夜のコンテストの問題 なんとか時間内に出来たけど、二部グラフの性質あたりがあやふやだったので自分用メモ

「頂点uからちょうど3本の辺を辿ることによって頂点vに辿り着けるような(u,v)をとって頂点uと頂点vを結ぶ」という操作を最大で何回繰り返せるか という問題

なかなか上手い方針が見えなかったが、長さ3のパスを長さ1に縮めることを繰り返してもパスの長さの偶奇はかわらないということに注目すればいい

すると奇数長のパスが存在する頂点間はいつか必ず結ばれるし、存在しない頂点間は永遠に結ばれないということがわかる

こういう話になると二部グラフの以下の性質が出てくる

「無向グラフGが二部グラフである⇔Gに奇数長の閉路が存在しない」

→の方は簡単で、二部グラフを2色で塗り分けてみると、元の頂点と奇数回動いたあとの頂点に塗られている色は違うはずで、閉路にはなりえない

←の方は、ある頂点sからの最短路が偶数長の頂点Aと奇数長の頂点Bに分けたとき、Aに含まれる頂点同士、Bに含まれる頂点同士が結ばれていることはない(∵奇数長の閉路は存在しない)ことからいえる

このことから、Gが二部グラフでないなら必ず奇数長の閉路が存在するということがいえて、この閉路で偶奇を調整すればどんな二頂点間にも奇数長のパスがあることになる

Gが二部グラフのときは2色で塗り分けられて、違う色で塗られた頂点同士は全て結べることになる

 

 

 こういう何もわからないときとりあえずいい感じの性質がないか探ってみるのは重要なのかも