https://cses.fi/problemset/task/1704 Please give any hints to this problem. I have been stuck for quiet a while.
Syrjälä's network consists of n computers and n−1 connections between them. It is possible to send data between any two computers.
However, if any connection breaks down, it will no longer be possible to send data between some computers. Your task is to add the minimum number of new connections in such a way that you can still send data between any two computers even if any single connection breaks down.
join nodes with degree=1 adjacently
It won't work definitely. I also stuck on this problem since yesterday. I know that the minimum number of edges to be added is equal to (number_of_vertices_with_degree_1 + 1)/ 2.But I am facing problem to how to choose the vertices to be added. One of my idea was joining the vertices with maximum difference of label between them where I label the vertices with dfs order. But it failed in one of the test cases.
If you join degree 1 nodes adjacently than removing one edge from that graph still result in traversal between two nodes.
But is it guaranteed that the number of edges to be added will be minimum possible?
Yes because adding edges to only those which have possibility of getting disconnected
I didn't get your approach. Can you share the idea briefly or the solution?
That's not correct. Consider this example n = 7, edges -
1 22 32 42 51 66 7According to you, min_number_of_edges = 2 but it's actually 3. Actually, you have to group those leaf nodes who do not have a common parent. Here 2 cases arise- 1. 2*max_leaf_node_component_having_common_parent > sum. In this case max_leaf_node_component_having_common_parent will be answer. 2. Else (leaf_node_count+1)/2 will be answer. Now I don't know how to actually associate these leaf nodes with edges. If you know, please tell me also.There 4 one degree nodes Therefore 3 edges
Add edges between
3 7and4 5.For your case it is sufficient to add edges between
3 7and4 5so the answer is definitely 2.I solved it. I ran dfs on the grpah and stored the vertices acc to that order. and than i joined the vertices int this way
for(int i=0;i<sz/2;i++) { cout<<arr[i]<<" "<< arr[sz/2+i]<<endl; }for odd no of vertices join the last vertice with the first. This soution got accepted butt i still cant figure out the proof for why this works.
it's late now but i hope this help :
We can see that when we add path to 2 leaf u v then we can break any connection on the simple path from u -> v without seperate the tree (call these edge visited edge)
assume that after this merging method there's some edge that's not visited:
case 1 : there're less than sz/2 leaf under this edge ==> some leaf inside must go out
case 2 : there're more than sz/2 leaf ==> either these leaf belong to the first or second half there must be at least 1 path be added from these leaf to another leaf
Algorithms Live! has a video with explained solution. First problem boils down to this problem and explanation is easy to follow.
snowden_007 AB.devil please see the video for better understanding.