グラフが良いことはその補グラフが二部であることと同値であることを示します。

補グラフをとると、条件は各部分集合がその半分以上のサイズの独立集合を含むことです。

奇数長のサイクルがあるなら、このサイクル内の頂点のみを考えると、最大の独立集合は半分より小さくなります。

一方、補グラフが二部であるなら、各部分集合に対して、「多数派」が半分以上のサイズの独立集合となります。

これを実装するには、\(m < \binom n2 -\lfloor\frac{n^2}4\rfloor\) なら直ちに No と出力し、そうでなければ愚直に確認します。これで \(O(m)\) 時間で済みます。あるいは \(n \ge 2002\) なら No と出力してもよく、これも間に合います。