AtCoder Grand Contest 067 A問題メモ

AtCoder Grand Contest 067

今回からRating対象が2000↑、5問体制となったAGC。
とりあえず今後もRatedで迎えたいね。

A - Big Clique Everywhere

• $1$ から $N$ までの番号がついた $N$ 頂点の単純無向グラフ $G$ が与えられます。
• $G$ は $M$ 本の辺を持ち、$i$ 本目の辺は頂点 $A_i$ と $B_i$ を結びます。
• $G$ が次の条件を満たすか判定してください。
  • 頂点集合 $\{1,2,\cdots,N\}$ のすべての部分集合 $X$ に対して、$X$ の部分集合 $Y$ であって $|Y| \ge \frac{|X|}{2}$ かつ $Y$ がクリークを形成するものが存在する。
  • ※クリーク_(グラフ理論)：誘導部分グラフが完全グラフとなるような頂点集合
• 解くべきテストケースは $T$ 個あります。

• $1 \le T \le 10^3$
• $1 \le N \le 10^5$
• $0 \le M \le 10^6$
• $1 \le A_i,B_i \le N$
• 与えられるグラフは自己辺も多重辺も含まない。
• ひとつの入力の中のテストケースすべてにわたる $N$ の総和は $10^5$ 以下である。
• ひとつの入力の中のテストケースすべてにわたる $M$ の総和は $10^6$ 以下である。
• すべての入力値は整数である。

いくつか例を考える。

• ①連結成分が3つ以上の場合
• 連結成分が2つの場合
  • ②2つがいずれもクリークの場合
  • ③それ以外
• 連結成分が1つの場合
  • ④全体を2つのクリークに分けられる場合
  • ⑤それ以外

①連結成分が3つ以上に分かれていると、そこから1点ずつ3点取ってきた $X$ が確実にアウト。

②連結成分が2つの場合、双方ともクリークであったらOK。
どのように $X$ を取っても、当然、半数以上の頂点はどちらかの連結成分に属する。
クリークの誘導部分グラフもクリークなので、多い方の連結成分由来の頂点がクリークをなす。

③逆に片方でもクリークでない場合、「同一連結成分で辺が無い頂点対 + もう片方の連結成分から1点」のような3点からなる $X$ がアウト。

④連結成分が1つの場合、全体を2つのクリークに分けられるなら、②と同じ理由でOK。

与えられたグラフが2つのクリークに分けられるかどうかの判定は 過去に類題があり、「補グラフが二部グラフなら可能」となる。

類題:ネタバレ注意

残る場合分け「⑤連結成分が1つで、2つのクリークに分けられないとき」を考える。

この時、補グラフに奇数長のサイクルが存在していることになる。
この奇数個の頂点を $X$ としてみる。

補グラフ上で互いに隣り合う頂点は同時に $Y$（クリークをなす頂点集合）に採用できないので、 最大でもサイクル上を1個飛ばしに採用するしかないが、奇数個の場合は $\frac{|X|-1}{2}$ 個までしか採用できず、条件を満たせない。

よって可能なのは②④のみとなり、結果的に連結成分数は関係なく、「グラフが2つのクリークに分けられること」=「補グラフが二部グラフであること」を判定すれば良いとわかる。

$N \le 10^5$ なので、辺数が多すぎて実際に補グラフを作れないような入力もあり得る。

$N$ と $M$ の関係から不可能と分かる入力は補グラフを作る前に判定する必要がある。

2つのクリークを作るのに必要な最小辺数は、頂点集合が均等に $\frac{N}{2}$ ずつに分かれるときに最も少なくなる。
$N$ が奇数の場合は1ずれるが、だいたい $\frac{N}{2}(\frac{N}{2}-1)$ が辺数の最小値となる。
よって、$M$ がこれ未満の場合は不可能。

この時、$M \le 10^6$ の制約から、可能な入力はおよそ $N \le 2000$ が満たされるので、 このサイズなら補グラフを作ることも可能となる。

Python3

def check_bipartite(n, links):
    """
    links[u] = { v1, v2, ... } のグラフが二部グラフであるかどうかを確認する。
    """
    color = [-1] * n
    for s in range(n):
        if color[s] != -1:
            continue
        q = [s]
        color[s] = 0
        while q:
            u = q.pop()
            cu = color[u]
            cv = cu ^ 1
            for v in links[u]:
                if color[v] == -1:
                    color[v] = cv
                    q.append(v)
                elif color[v] == cu:
                    return False
    return True


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())

    a = n // 2
    b = n - a
    lower_limit = a * (a - 1) // 2 + b * (b - 1) // 2
    if m < lower_limit:
        for _ in range(m):
            input()
        print('No')
        continue

    links = [set(range(n)) - {i} for i in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        links[u].remove(v)
        links[v].remove(u)

    if check_bipartite(n, links):
        print('Yes')
    else:
        print('No')