アルゴリズム忘備録

競技プログラミングとかデータ分析とか

Codeforces Round #429 D. Leha and another game about graph

Problem - D - Codeforces

 

無向連結グラフが与えられる。自己ループはないが二重辺は存在する。各頂点iにはd[i]=0 or 1 or -1 という数が割り当てられている。このグラフのサブグラフを構成して、degree(i) % 2 = d[i] or d[i] = -1 を満たす、つまり、0または1の場合は頂点の次数のmod2にd[i]が一致するようにしたい。このようなサブグラフが存在するか?存在するならば具体的に構成せよ。

 

-1の頂点がない状況を考える。頂点次数のmod 2がd[i]と一致している頂点を「正しい頂点」、一致していない頂点を「正しくない頂点」と定義すると、正しくない頂点同士を結んだエッジは取り除いて除去することができる。また、正しい頂点と正しくない頂点を結ぶエッジは取り除くことによって、正しいと正しくないをSwapすることができる。

 

そこで、ある頂点を根とする全域木を考える(と言っても単に未訪問の頂点をdfsで辿っていくだけである)このとき、正しくない頂点が根から遠いところにある場合は、根の方向のエッジを取り除く(この取り除いたエッジのインデックスはメモしておく)。すると、エッジの両端は正しい頂点になるか、または根に近いほうが正しくない頂点になる、のいずれかになる。これを葉から再帰的に行うことで、最終的に根が正しい頂点になっていれば構成可能ということで、メモしておいたインデックスを除くサブグラフを出力する。

 

次に-1の頂点が1個以上ある場合、同じような考え方で、正しい頂点とみなしておくが、もし接続されたエッジを取り除いたあとも正しい頂点のままとみなしておく。ただし、この時根が正しくない頂点になっていても、-1の頂点に向かって正しくない頂点を移動してけば構成可能になる。このような判定をしないために、元から根として-1が割り振られた頂点を選んでおくと、最終的に根のところは常に構成可能になる。つまり、-1の頂点が1個以上ある場合、常に構成可能になる。O(V)。