A - Big Clique Everywhere / Time Limit: 4 sec / Memory Limit: 1024 MB 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,⋯,N}, there exists a subset Y of X such that ∣Y∣≥ 2 ∣X∣ and Y forms a clique. You have T testcases to solve. Constraints 1≤T≤10 3 1≤N≤10 5 0≤M≤10 6 1≤A i ,B i ≤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 ⋮ case T Each test case is given in the following format: N M A 1 B 1 A 2 B 2 ⋮ 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 1 Copy 4 3 3 1 2 1 3 2 3 3 2 1 2 1 3 3 1 1 2 3 0 Sample Output 1 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.
理解问题A - Big Clique Everywhere / Time Limit: 4 sec / Memory Limit: 1024 MB 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,⋯,N}, there exists a subset Y of X such that ∣Y∣≥ 2 ∣X∣ and Y forms a clique. You have T testcases to solve. Constraints 1≤T≤10 3 1≤N≤10 5 0≤M≤10 6 1≤A i ,B i ≤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 ⋮ case T Each test case is given in the following format: N M A 1 B 1 A 2 B 2 ⋮ 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 1 Copy 4 3 3 1 2 1 3 2 3 3 2 1 2 1 3 3 1 1 2 3 0 Sample Output 1 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.
已完成理解「A - Big Clique Everywhere / Time Limit: 4 sec / Memory Limit: 1024 MB 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,⋯,N}, there exists a subset Y of X such that ∣Y∣≥ 2 ∣X∣ and Y forms a clique. You have T testcases to solve. Constraints 1≤T≤10 3 1≤N≤10 5 0≤M≤10 6 1≤A i ,B i ≤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 ⋮ case T Each test case is given in the following format: N M A 1 B 1 A 2 B 2 ⋮ 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 1 Copy 4 3 3 1 2 1 3 2 3 3 2 1 2 1 3 3 1 1 2 3 0 Sample Output 1 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.」
展开阅读网页
- 判断图是否满足特定条件。
问题描述
给定一个简单无向图 $ G $，顶点编号从 1 到 $ N $，包含 $ M $ 条边。对于顶点集合的任意子集 $ X $，需要判断是否存在子集 $ Y $ 使得 $ |Y| \geq 2 \times |X| $ 并且 $ Y $ 构成团（clique）。
输入格式
- 第一行：测试用例数量 $ T $。
- 接下来每组测试用例包含：
- 第一行：顶点数 $ N $ 和边数 $ M $。
- 接下来 $ M $ 行：每行两个整数 $ A_i $ 和 $ B_i $ 表示一条边。
输出格式
- 对于每个测试用例，如果图 $ G $ 满足条件，输出 "Yes"，否则输出 "No"。
约束条件
- $ 1 \leq T \leq 10^3 $。
- $ 1 \leq N \leq 10^5 $。
- $ 0 \leq M \leq 10^6 $。
- $ 1 \leq A_i, B_i \leq N $。
示例输入输出
- 示例输入 1：
- 4
- 3 3
- 1 2
- 1 3
- 2 3
- 3 2
- 1 2
- 1 3
- 3 1
- 1 2
- 3 0
- 示例输出 1：
- Yes
- Yes
- Yes
- No
算法思路
- 由于题目要求对于任意子集 $ X $ 都存在满足条件的子集 $ Y $，实际上可以简化问题为判断图中是否存在一个顶点，它与 $ X $ 中至少一半以上的顶点相连。如果存在这样的顶点，则对于任意 $ X $，都可以取 $ Y $ 为该顶点和它相连的顶点集合，满足 $ |Y| \geq 2 \times |X| $。
- 遍历所有顶点，对于每个顶点，统计它的最大度数（即与多少个其他顶点相连）。
- 如果存在一个顶点的度数大于 $ N/2 $，则满足条件，输出 "Yes"；否则，输出 "No"。
代码实现
T =
