CF1835F.Good Graph
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a bipartite graph G with the vertex set in the left part L , in the right part R , and m edges connecting these two sets. We know that ∣L∣=∣R∣=n .
For any subset S⊆L , let N(S) denote the set of all neighbors of vertices in S . We say that a subset S⊆L in graph G is tight if ∣S∣=∣N(S)∣ . We say that graph G is good if ∀S⊆L,∣S∣≤∣N(S)∣ .
Your task is to verify whether the graph is good and, if so, to optimize it. If the graph is not good, find a subset S⊆L such that ∣S∣>∣N(S)∣ . However, if the graph is good, your task is to find a good bipartite graph G′ with the same set of vertices L∪R , in which ∀S⊆L , S is tight in G if and only if S is tight in G′ . If there are multiple such graphs, choose one with the smallest possible number of edges. If there are still multiple such graphs, print any.
输入格式
The first line of the input contains two integers n and m ( 1≤n≤103 , 0≤m≤n2 ), separated by a single space. The number n denotes the number of vertices in each of the sets L and R , and the number m denotes the number of edges between them.
The following m lines describe the edges. Each of them contains two integers l and r ( 1≤l≤n , n+1≤r≤2⋅n ), separated by a single space, indicating that there is an edge from vertex l∈L to vertex r∈R .
输出格式
If the graph G given in the input is not good, output one word "NO" in the first line of the output. In the second line of the output, output the number k , and in the third line, output k numbers l1,l2,…,lk , separated by single spaces. These numbers should indicate that for the set S={l1,l2,…,lk} , ∣S∣>∣N(S)∣ .
However, if the graph G given in the input is good, output one word "YES" in the first line of the output. In the second line of the output, output the number m′ , indicating the number of edges in the new, also good graph G′ . Then, in the following m′ lines, output the edges of the graph G′ in the same format as given in the input.
输入输出样例
输入#1
3 8 1 4 1 5 1 6 2 4 2 5 2 6 3 5 3 6
输出#1
YES 6 1 4 1 5 2 5 2 6 3 6 3 4
输入#2
3 4 1 4 1 5 2 6 3 6
输出#2
NO 2 2 3
说明/提示
In the first sample test, the graph G is good; thus, we are looking for an equivalent graph with the same tight sets. The only tight set is {1,2,3} , which remains tight in the resulting graph. Moreover, no other set is tight in the resulting graph. One can prove that no graph with less than 6 edges and the same tight sets exists.
In the second sample test, the graph G is not good. Set {2,3} has only one neighbour — vertex 6 . Thus, ∣{2,3}∣>∣{6}∣ , which is a prove that the input graph is not good.