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

code-festival-2017-qualb.contest.atcoder.jp

グラフが与えられる。辺をちょうど3回通ってたどり着ける2点間に新たに辺を引く、という操作をできるだけしたい。ただし、既に辺がある場合は引くことができない。最大で何回操作ができるか？

グラフが二部グラフでないとき、頂点間の経路は操作を繰り返していくことで、すべての2点間で3回通って辿り着ける。そのため、完全グラフの辺の数から既に引かれている辺の数を引けばよい。

グラフが二部グラフの場合、最大で完全二部グラフにしかならない(偶奇を考えればよい)。そのため、完全二部グラフの辺の数から現在引かれている辺の数を引けば良い。

計算量は二部グラフの判定が支配項でO(N)。