### ksb_451's blog

By ksb_451, history, 13 months ago,

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.

• +4

 » 13 months ago, # |   0 join nodes with degree=1 adjacently
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 13 months ago, # ^ |   0 If you join degree 1 nodes adjacently than removing one edge from that graph still result in traversal between two nodes.
•  » » » » 13 months ago, # ^ |   0 But is it guaranteed that the number of edges to be added will be minimum possible?
•  » » » » » 13 months ago, # ^ |   0 Yes because adding edges to only those which have possibility of getting disconnected
•  » » » » » » 13 months ago, # ^ |   0 I didn't get your approach. Can you share the idea briefly or the solution?
•  » » » » » » » 13 months ago, # ^ |   0 Since it is a tree if there exist a node with degree=1 than disconnecting the connected edge with this node results in a lonely node. And no path exist with this node
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 That's not correct. Consider this example n = 7, edges - 1 2 2 3 2 4 2 5 1 6 6 7 According 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.
•  » » » » 13 months ago, # ^ |   0 There 4 one degree nodes Therefore 3 edges
•  » » » » » 13 months ago, # ^ |   0 Add edges between 3 7and 4 5.
•  » » » » 13 months ago, # ^ |   0 For your case it is sufficient to add edges between 3 7 and 4 5so the answer is definitely 2.
•  » » » 13 months ago, # ^ |   0 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
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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
 » 13 months ago, # |   +7 Algorithms Live! has a video with explained solution. First problem boils down to this problem and explanation is easy to follow.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 snowden_007 AB.devil please see the video for better understanding.