 Practice

Contest

Easy-Medium

Construction

# Problem:

Connect N nodes of the graph with M edges such that:

1. The graph is biconnected.

2. 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.

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.

1. 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.
2. 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

Why 2 1 not available in the testcase of the1st subtask ? And Why I am getting WA for first subtask ?

Why 2 1 not available in the testcase of the1st subtask ? And Why I am getting WA for first subtask ?

UPD: It’s still not fixed in practice. Don’t let problems be broken!

For N=M=4, different ways to print a cycle of length 4 give AC or WA. Examples (edge lists):

1-2,2-3,3-4,1-4: AC

1-2,2-4,3-4,1-3: WA

1-2,2-3,1-4,3-4: AC

1-2,2-4,1-3,3-4: WA

Also, my solution: apart from special cases of N \le 3, take vertices 1, N and connect them through multiple paths containing some vertices - for example \texttt{1-2-6,1-3-6,1-4-5-6} (N=6,M=7). If there are p such paths, there are N-2+p edges and 2 \le p \le N-2, so it works for N \le M \le 2N-4.

The graph is clearly 2-vertex-connected. If we remove an edge, then a leaf appears and either 1 or N definitely becomes an articulation.

I have a proof that 2N-3 is the maximum possible M. Let’s take a graph, root it and find its DFS spanning tree. The absence of articulations means that from each subtree, there’s a back edge (an edge from some vertex in the subtree to its ancestor) going above that subtree; this is also a sufficient condition. However, if there are two or more back edges from a single vertex, we can remove the one that goes to a lower ancestor and that condition will still hold. In addition, the root has no back edge and there’s at least one son of the root (in fact, there must be exactly one so that the root wouldn’t be an articulation) with no possible back edge, which means there are \le N-1+N-2=2N-3 spanning tree edges + back edges.

The proof that M=2N-3 is impossible could use the fact that there’s exactly one back edge from each vertex in that case (for any choice of root and ordering of edges in the DFS), so the graph would have to be very special.

3 Likes

In the proof of your lemma 2 you have only proved: “If there is a cycle chord => it does not satisfy the requirements” contrapositive of which is “it satisfies the requirements => there is no cycle chord”. So the second part holds agreed.

For the first part " graph doesn’t contain cycle chords => it satisfies the requirements " you can do:

1. assume graph has no chords. Now try and prove that it satisfies the requirements.
2. Assume graph does not satisfy the requirements. Now prove that there is a chord.

Can you please provide an explanation in this regard?

Also : "It can be proved by induction that the maximal number of edges in the graph satisfying the conditions for the particular N≥4 is 2⋅(N−4). ". Please provide a proof of this statement.
I think the correctness of this answer depends on this statement.

1 Like

Why testcase 2 1 doesn’t have solution? Which requirement is broken for Solution “1 2” (two computers connected)

1 Like

This caused me wrong answer for larger testcase.
https://www.codechef.com/viewsolution/9025772

Should be re-evaluated.

I still don’t know why my solution get WA in task #2 of subtask #2: https://www.codechef.com/viewsolution/9029567

Question says:

even if any one computer from the network gets disabled so that the rest of the computers are unable to communicate with it, the rest of the computers can still communicate with each other.


Editorial says:

There is no such edge that after its' removal the first requirement violates.


Both are different. Question asks to take care of removing a node and the editorial’s solution is for removing an edge.

The question says that second line also in the second requirement.

the rest of the computers can still
communicate with each other. In other
words, the first requirement still
holds for any subset of (N-1)
computers.

A Solution to fetch you 21 points can be to consider case:2 1 ,here only 1 connection is required.Also for any other value of n and m,if they are equal only then it will work ie if n==m then: write (i i+1) for i=1;i<n-1;i++
write (n 1)

@aman935
It says N-1 computers not N-1 connections. So there is contradiction between question and editorial.

here is my solution.
https://www.codechef.com/viewsolution/9042616
saample input
1
5 6
output:
1 2,
2 3,
3 4,
1 4,
5 1,
5 4

I think this output is not right because…
when i remove the edge between 1-4 they stil remaining cycle which breaks the third condition.
Am i right or wrong , data set is wrong or right??

Why is the code of setter and tester not opening? Is it me or everyone? Please let me know

@xellos0.: Can you please check whether the setter or tester’s code is opening or not? I am trying for almost an hour…thanks

For the 2 1 testcase, Requirement 2 will be brocken. Note that if one of them is disabled due to attack,then the case reduces to 1 1 which then breaks requirement 3.
Note that multiple connections between any pair of computers and connections connecting a computer to itself are implicitly not allowed due to the third requirement.”- As stated in Problem statement

IMHO taking one computer away reduces 2 1 to 1 0, which in fact satisfies all requirements.
The dangling edge edges should be removed when removing one node. Otherwise uneccessary edges would always be left over during a reduciton

1 Like