Are extra edges same as bridges in a component? I mean isn’t it equals to the number of cycles?
No my first idea was to find bridges, but then realized all trees will have exactly n-1 edges hence all extra edgdes are redundant. We can remove m-(n-1) edges from each connected component. There isn’t any need of bridges here.
I would like to share my approach, though I was not able to implement this efficiently in time so got only 60. My method is similar to Editorialist.
This is just theoretical part and I'm not going into implementation.
First we consider all the graph into its all connected components. I’ve divided the components into three types-
Type-1
Component with Redundant Edges (Non-Tree) - If there are x nodes in this component, then the edges will be x-1+ \delta where \delta>0. It is basically a component with cycles.
In the above diagram, no. of nodes in the component are 5. So only 4 edges were sufficient for this component to be intact. So, other 4 edges out of 8 are redundant.
Type-2
Component with no Redundant Edges (Tree) and nodes>1 - If there are x nodes in this component, then the edges will be x-1. Here, x>1. There will be no cycles
In the above diagram, nodes are 7 are edges are 6.
Type-3
Same as second Component but with x=1 or simply free nodes.
Okay, So we are done with all the components. Let’s proceed.
Step-1
To join any two components of Type-1, we have to pay 0 cost and after joining them, if there were x redundant edges in the Component-1 and y redundant edges in Component-2, the redundant edges in their fusion will be x+y-1.
So, we can say the fused component will always have at-least 1 redundant edge. How??
x>=1 and y>=1. So, minimum value of the x+y-1 is 1.
In the above diagram you would notice that Component-1 has 2 redundant edges and Component-2 has 2 redundant edges. After joining, the final component has 3 redundant edges and degree of no node is changed. So, cost=0.
Similarly, we can extend this idea to join all the components of Type-1.
If there are i such components with count of redundant edges as e_1, e_2, e_3, ... e_i, then we can join them all and redundant edges in final component will be (e_1+e_2+ e_3+ ... + e_i) -(i-1). We can say the previous expression is always >=1. So, number of redundant edges in final component is always >=1. Let’s call the final Component as Master Component in the next discussion.
Step-2
Let’s try to join Master Component with any Component of Type-2.
Master Component has redundant edges (at-least 1) and component of Type-2 is a tree and hence, no redundant edges. We can join them with cost=0.
Earlier, Master Component had 3 redundant edges, but after joining it with a component of Type 2, redundant edges reduce to 2. So, we can add 2 more Components of Type-2 such that we don’t change the degree of any node. After that the master component will will also become a tree and to add more trees we have to pay cost=2 per adding another tree.
Step-3
Now, if we want to join Master Component with a free node. We have to pay cost=2.
So, if there are x free nodes, do we have to pay 2 \cdot x ?? … No, we can do better. We can join them with cost=2 \cdot (\lfloor \frac{x}{2}\rfloor + x \% 2) (Considering there are sufficient redundant edges to join all).
We are making pairs of free nodes and after making all pairs, if one free node is still left we have to join it to the master component with cost=2. At each step of joining we’ll reduce number of redundant edges in master component by 1.
What if ??
What if we lose all the redundant edges in the master component and we are still left with components of Type-2 or 3 ? Then we have to add these components one by one with cost=2 at each step
What if ??
What if there was no Type-1 Component in the original graph ? Now only Type-2 or Type-3 Components are there and if x is number of Type-2 or Type-3 components, the cost we have to pay cost =2 \cdot (x-1).
7 Likes
this should have been the editorial
1 Like
See my code it is very simple ,I used some simple vector pair and solve this problem with some greedy algorithm without using graph or tree.
1 Like
Mind blowing question and editorial i hope some day i also will be able to solve these types of problems during the contest