Codeforces solution explain

#1

Question:
https://codeforces.com/problemset/problem/1242/B
Tutuorial:
https://codeforces.com/blog/entry/71216
Can you explain its soloution ?

#2

@Kapil-Israni-2501896056550976 The required minimum graph wants you to have maximum number of 0-weight edges in it, so we need to focus on how we can minimise the number of 1-weight edges .
Therefore we try to find all the sub-connected graphs considering only the 0-weight edges.
Now lets say you have k such components and because the graph is complete the remaining edges connecting these components must have weight 1. Therefore the answer is k-1.
We find these components using the complement of graph that we construct using the 1-weight edges.
Check this implementation https://ide.codingblocks.com/s/192389
I have added comments to this.

1 Like
#3

“Now lets say you have k such components and because the graph is complete the remaining edges connecting these components must have weight 1. Therefore the answer is k-1.” … Please can you elaborate this line, could not follow up.

#4

Let’s consider this testcase.There are only 3 nodes . Edges between them are as follows
1->2 has weight 0
1->3 has weight 1
2->3 has weight 1
Now like I said try to form the graph with only edges having 0-weight.
The graph currently is divided in two components.
One component has 1 and 2 because they are connected by edge having weight 0
Second component having node 3.
so k=2 in this case.
Now to connect these two components we need to edge with weight 1 because we have no other choice.
And we only need one edge , we can use wither 1->3 or 2->3 ,it doesn’t matter, what matters is that we only need 1 new edge. And in this 1=(k-1).
That is why we need k-1 edges to connect k components.

#5

@Kapil-Israni-2501896056550976 If you don’t have any further queries, please mark the doubt as resolved.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like