xennygrimmato's blog

Faster method to make graph disconnected
By xennygrimmato, 10 years ago, In English

For a problem that I am solving, I need to sort in descending order all edges by weight and keep removing edges till the graph becomes disconnected.

I am performing DFS after removing every edge, to check if the graph is disconnected. So, the time complexity of this method is O(NM).

Is there any way in which I can perform the above task faster?

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Sort the edges in ascending order, then start adding edges to your graph until it becomes connected. You can use dsu for it. The total running time will be O(MlogM + Mα(N)).

Edit. This solution may be wrong, I think I'm missing something important and came too fast to a conclusion.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The graph won't always be a tree after removing the edges. For example consider a graph where the edge with the largest cost is a bridge.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Yeah, you're right, I realized it after writing my post. I should think more carefully before writing something.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        it's correct you give up too easily

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Then it wouldn't get connected until we add the edge with the largest cost i think you didnt understand his solution

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I think you didn't understand the problem. when we remove this edge the graph will be disconnected and we we'll stop removing edges.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          And in yosei-san's solution we add edges until the graph is connected that means we add edges until we are gonna add the last edge which makes the graph connected

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            My bad, you're right. I misunderstood his solution I thought he's trying to get the MST of the graph.

            → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +25 Vote: I do not like it

            Damn, I'm too unsure of myself. Here's a somewhat "legit" proof of why this procedure is correct.

            Consider the procedure of removing edges with highest cost, until our graph is decomposed into 2 distinct connected components. After doing this we are left with a set of edges that determine our resulting graph that is not connected, call this set S with k elements that contains the first k edges by increasing weight.

            Now consider building the graph from the bottom, using the edges in ascending order. Because the edges are sorted by increasing weight, our procedure will first consider all the edges from S and our graph will remain disconnected while we do this, then when we will consider the first edge that is not in S it will become connected as a consequence of the first procedure.

            → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think I know the basic operations of DSU, but I am unable to understand how can I find out when does the graph become connected. I'll have to check if the parents of all nodes become common right? So I'll have to check parents of all the N nodes after adding each edge. Wouldn't that take O(Mlog(M).N) ? Please tell me where I am wrong in understanding.

    In short, how exactly are we supposed to check whether the graph has become connected or not?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Keep a counter that tells you how many connected components there are in the graph (it's initially N). So, when you do a "union_set" operation, if you are joining two different components you just decrement this counter by one. If the counter becomes 1 that means all nodes are in the same component and therefore the graph is connected.

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

Binary search?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

    Think more before saying. There is a much simple+effective solution. This solution is also mentioned in one of above comments.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      I was just suggesting an alternate solution -- after all, both solutions have complexity. Some people might find binary search more intuitive.

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

    How do we apply binary search to remove a set of edges, in your method? Can you be more specific on how binary search is supposed to be applied here?

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

      Do a binary search over the number of edges that we need to remove. Let's say that the current candidate is k. Build a graph with all edges except of the last k and check if the graph is connected or not.

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

pls dont violate the rules of a running contest

http://www.codechef.com/APRIL15/problems/DIVLAND

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

    This blog post is not intended to be related to that problem. The problem I mentioned is a sub-problem in one of my college assignments. If it does violate the rules of that contest, I don't mind removing the blog post :)

    → Reply