Codeforces Round 311 D Vitaly and Cycle

問題

http://codeforces.com/contest/557/problem/D
多重辺や自己ループを含まないグラフが与えられる。またこのグラフでは辺の重みは全て1として考える。
この辺にいくつか辺を追加して長さ奇数の閉路(ただし自己ループではない)を一つ以上含むグラフにしたい。ただし元々辺があるノード間に新たに辺を追加するのはできない。

最小何本の追加で達成できるか。またその最小本数の追加は何通りあるか。

解法

入力で与えられるグラフの頂点数をn,エッジ数をmとする。
追加する最小本数tは0,1,2,3のどれかである。
グラフの最大次数が0の時、辺は1本もないのでt=3で、追加の仕方は全部の頂点から3個選んだ通りになるのでnC3となる。
グラフの最大次数が1の時、長さ3の閉路を作ればよく、この時t=2である。この時は辺とその辺に含まれない頂点の中から1個選べば良いのでm*(n-2)である。
それ以外の時、BFSまたはDFSによってグラフに奇数の閉路がないか調べる。あった場合はt=0で追加の仕方は1通り。奇数の閉路があった場合、頂点を2色で塗り分けて同じ色どうしの頂点をエッジで結べば長さ奇数の閉路ができるので n1 chose 2 + n2 choose 2で計算できる。ただしn1,n2はそれぞれ色1,2で塗られた頂点の個数。