ksb_451's blog

Network Renovation CSES Problem set
By ksb_451, history, 4 years ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

join nodes with degree=1 adjacently

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you join degree 1 nodes adjacently than removing one edge from that graph still result in traversal between two nodes.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But is it guaranteed that the number of edges to be added will be minimum possible?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes because adding edges to only those which have possibility of getting disconnected

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I didn't get your approach. Can you share the idea briefly or the solution?

            → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There 4 one degree nodes Therefore 3 edges

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For your case it is sufficient to add edges between 3 7 and 4 5so the answer is definitely 2.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Algorithms Live! has a video with explained solution. First problem boils down to this problem and explanation is easy to follow.

→ Reply