CF1835F Good Graph

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 \subseteq L $ , let $ N(S) $ denote the set of all neighbors of vertices in $ S $ . We say that a subset $ S \subseteq L $ in graph $ G $ is tight if $ |S| = |N(S)| $ . We say that graph $ G $ is good if $ \forall_{S \subseteq L}, |S| \leq |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 \subseteq 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 \cup R $ , in which $ \forall_{S \subseteq 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.

N/A

N/A

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.