Problem Link:
Difficulty:
Easy-Medium
Pre-requisites:
Construction
Problem:
Connect N nodes of the graph with M edges such that:
-
The graph is biconnected.
-
There is no such edge that after its’ removal the first requirement violates.
Explanation:
Solution for the subtask 1 (21 points):
It’s obviously impossible to build a graph with such restrictions if N \leq 2.
Note, that if there is a solution, then N \leq M.
Let N = 3. The only way to connect all vertices satisfying given conditions is to build a cycle, consisting of N = M = 3 nodes.
Let N = 4. The only way to connect all vertices satisfying given conditions is to build a cycle, consisting of N = M = 4 nodes. If we will try to add new edge, the 2nd requirement won’t be held.
Another way to solve this subtask was a brute force solution: just iterate through all variants to create a graph with N nodes and M edges and check each of them. Literary, anything was supposed to pass this subtask - even drawing all variants on paper and computing the answer to the problem manually.
Solution for all subtasks:
Lemma 1. If G is a biconnected graph and ab is an edge between nodes a and b, and G-ab is not biconnected. Then, a and b belong to different blocks of the graph G-ab.
Lemma 2. The graph will satisfy all the requirements iff is doesn’t contain cycle chords.
Proof.
- let’s prove that the connected graph doesn’t containin cycle chords => it satisfies the requirements. Consider the opposite. If there is a cycle chord ab, let’s remove it. Then, if the graph loses the biconnection property, nodes a and b belong to the different blocks. But there is still a cycle, containing both a and b, so they can’t belong to the different blocks => contradiction. So, the statement is now proved.
- Let’s prove that the connected graph satisfied the requirements => it doesn’t contain cycle chords. Consider it contains a cycle chord. Then, using the same logic as in the previous part of the proof, we obtain that the graph can’t contain cycle chords.
Consider a cycle of K nodes and K edges, where K \geq 4.
Let us add the new (K+1)th node and connect it to any two non-adjacent nodes of the graph.
As you can see, given that the previous graph was correct, after this step, the graph still holds all the requirements.
This way, we can convert a graph containing X vertices and Y edges to the graph containing (X+1) nodes and (Y+2) edges.
Now, consider we want to build a graph containing N nodes and M edges.
Initially, let’s take a cycle of K nodes. It will contain K edges as well. Then, let’s apply the step described above. Each applying of this step will add 1 node and 2 edges, so for the fixed K the number of steps should be N-K. Based on this, we can derive with a simple equation for determining K:
(N - K) \cdot 2 = M - K
Therefore, K = 2N - M.
It can be proved by induction that the maximal number of edges in the graph satisfying the conditions for the particular N \geq 4 is 2 \cdot N - 4. The provided approach works for all such M.
The complexity is O(N + M) for a single test case.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here