noobinho's blog

Graph problem
By noobinho, history, 6 years ago, In English

I'm trying to do this problem: http://acm.timus.ru/problem.aspx?space=1&num=1416. It consists in a simple, undirected and weighted graph for which is demanded to calculate the second minimum total cost: a cost of a configuration (different than the minimum-spanning-tree) which connects all vertex and has the smallest cost not less than the cost given by the minimum-spanning-tree. If there isn't such a configuration it's demanded to indicate that. I did the following code: https://ideone.com/e.js/y4CcBz. It generates the minimum-spanning-tree with Kruskal and tries to eliminate the edges of this tree one by one from the bigger to the smallest. For each edge eliminated, it tries to connect the edges that weren't in the minimum-spanning-tree, one by one, from the bigger to the smallest, and verifies with a DFS if the resulting graph has only one connected component. If so, it stops. Else, it reconnects the edge of the minimum-spanning-tree and goes to the next iteration. Since my approach gives wrong answer, I want to know what is wrong with it and what is the correct approach. Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

How to find 2nd Minimal Spanning Tree? At first, let's build MST. Consider all edges that doesn't belong to MST. We can try to add them independently to MST. YEA, we've got a cycle. We can erase any edge in a cycle and rest edges will be Spanning Tree. Obviously, it's good idea to erase edge with maximal weight (and this edge mustn't be our added edge, off course:) ). Then relax our answer.

Code: https://pastebin.com/TraXQSY0

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

    Thank you very much, I got your approach!

    But I still would appreciate knowing why my initial approach doesn't work. Could someone provide some test case where it fails, please?

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

      Your solution fails on this test:

      4 5

      1 3 1

      2 3 2

      2 4 1

      4 3 1

      1 4 1

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

    Please explain how to find the maximal weighted edge in the cycle formed by adding the new edge.

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

      In this problem N <= 500, so you can do it in a stupid way.

      For example, you add edge (u, v). Find lca(u, v) and consider all edges on the way from u to lca and from v to lca. take maximal.

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

By the way, there is, perhaps a simpler solution: find a mst, then for each edge from the mst to find a mst in the graph without it, the answer is the minimum of the resulting mst.

upd: I did not quite understand the constraints in the problem, so maybe this solution is too slow

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

    I think it would be O(E²*logV). The problem didn't give the constraint to the total of edges but in the comments at the forum of the online judge someone argued that he tested and found out that the edges can be 250000 in a test case. So, it probably wouldn't pass.

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

      but note in the mst only O(V) edges, and you can search for mst O(E * α(E, V)), so it will be O(V * E * α(E, V))

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

        I didn't understand. How do you search for mst?

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

          I already got a AC so that you can just see the code) https://pastebin.com/J3XWnPCP

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

            If I understood, you ran Kruskal one time for the total graph to get ans1 and after, for each edge that was in the MST, you ran Kruskal for the total graph without it and took the minimum of the total costs to get ans2. So it would be O(E*V*logV). Is it correct?

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

              everything is correct, except the complexity of the algorithm) Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in O(E*α(V)) time , where α is the extremely slowly growing inverse of the single-valued Ackermann function. (it's from wiki) p.s (we can assume that α(V) is always < 5)

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

                By the page 452 of Cormen's book second edition, the complexity is O(E*α(V)) in time if you consider that the disjoint-set data structure utilizes the heuristic of union by rank and path compression (which you are already using) and that |E| >= |V| — 1 (which is true by the statement of the problem). In the same part of the book, the author says that α(|V|) = O(logE) and concludes that the total time execution for Kruskal algorithm is O(E*logE). If we consider in addition that |E| < |V|² (which isn't the case in this problem), than log(|E|) = O(logV) and we can redefine the time of execution to O(E*logV). So, I think the complexity of your algorithm would be O(E*V*logE).

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

                  Indeed, the α(n) = O(log (n)) (and α(n) = O(n!) :) ). But for any n not exceeding 10^600, α(n) < 5

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

                  So, we could consider your algorithm as O(E*V) in time for practical purposes?

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

                  I think yes

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

                  as I know, usually this is written as O(V*E*α), meaning V*E*const

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

about your solution: on the test "2 2 1 1 1 2 2 2" it displays "0, -1", is this normal?

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

    By the statement of the problem, I think this case is impossible. Anyway, my initial approach is too inefficient and I already discarded it.

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

      it seemed to me that your solution works for O(VE), is not it?

      → Reply