A - Big Clique Everywhere

Contest Duration: 2024-08-18(Sun) 12:00 - 2024-08-18(Sun) 15:00 (local time) (180 minutes) Back to Home

A - Big Clique Everywhere Editorial

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

$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$ 以下である。
すべての入力値は整数である。

入力

入力は標準入力から以下の形式で与えられる。

 $T$ 
 $case_1$ 
 $case_2$ 
 $\vdots$ 
 $case_T$

各テストケースは以下の形式で与えられる。

 $N$   $M$ 
 $A_1$   $B_1$ 
 $A_2$   $B_2$ 
 $\vdots$ 
 $A_M$   $B_M$

出力

各テストケースについて、 $G$ が条件を満たすなら Yes、そうでないなら No と出力せよ。
Yes または No の出力において、各文字は大文字・小文字のいずれでもよい。

入力例 1Copy

Copy

出力例 1Copy

Copy

Yes
Yes
Yes
No

$1$ 番目のテストケースについて、 $G$ は条件を満たします。この場合、すべての部分集合 $X$ がクリークであるため、単に $Y=X$ とできます。

$2$ 番目のテストケースについて、 $G$ は条件を満たします。例えば、 $X=\{2,3\}$ に対しては、 $Y=\{2\}$ とできます。

$4$ 番目のテストケースについて、 $G$ は条件を満たしません。 $X=\{1,2,3\}$ とすると、条件を満たす $X$ の部分集合 $Y$ はありません。

Score : $600$ points

Problem Statement

You are given a simple undirected graph $G$ with $N$ vertices numbered $1$ to $N$ . $G$ has $M$ edges and the $i$ -th edge connects vertices $A_i$ and $B_i$ .

Check if $G$ satisfies the following condition:

For every subset $X$ of the vertex set $\{1,2,\cdots,N\}$ , there exists a subset $Y$ of $X$ such that $|Y|\ge \frac{|X|}{2}$ and $Y$ forms a clique.

You have $T$ testcases to solve.

Constraints

$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$
The given graph doesn't contain self-loops or multiple edges.
The sum of $N$ across the test cases in a single input is at most $10^5$ .
The sum of $M$ across the test cases in a single input is at most $10^6$ .
All input values are integers.

Input

Input is given from Standard Input in the following format:

 $T$ 
 $case_1$ 
 $case_2$ 
 $\vdots$ 
 $case_T$

Each test case is given in the following format:

 $N$   $M$ 
 $A_1$   $B_1$ 
 $A_2$   $B_2$ 
 $\vdots$ 
 $A_M$   $B_M$

Output

For each test case, if $G$ satisfies the condition, print Yes, and otherwise print No.
In printing Yes or No, you can output each letter in any case (upper or lower).

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Yes
Yes
Yes
No

For the $1$ -st test case, $G$ satisfies the condition. In this case, every subset $X$ is a clique, so we can just let $Y=X$ .

For the $2$ -nd test case, $G$ satisfies the condition. For example, for $X=\{2,3\}$ , we can let $Y=\{2\}$ .

For the $4$ -th test case, $G$ doesn't satisfy the condition. If we let $X=\{1,2,3\}$ , no subset $Y$ of $X$ satisfies the condition.