jarvis307's blog

Connected Components in Compliment Graph ?
By jarvis307, history, 4 years ago, In English

Hello Codeforces!!

I was doing the question 1242B - 0-1 MST. Similar type of questions are 920E - Connected Components? 190E - Counter Attack.

In short, these questions ask you to calculate the number of connected components in the compliment of graph.

I have read the editorials but I am a little stuck with the problem.

I would be grateful if someone could help me out with this.

TIA

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

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

hmm, in my thougth, this problem is prim's algorithm, not kruskal if you try kruskal, O(n^2) because you need to sort edge. in this method, you need to see zero weight edge before see one weight edge

prim: node is center kruskal: edge is center

so, if there are so many edge kruskal is time out (so, almost every kruskal problems give you max edge size)

prim is "node center" so you don't have to see all edge, go prim!

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

    You may still have to look at way too many edges with Prim. These problems aren't such straightforward applications of MST algorithms.

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

      Can you please share your approach if you have some!!

      TIA!!

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

        Pick the vertex with the smallest degree. Every vertex that is not connected to it is connected to it in the complement, we can squeeze these into a single vertex. Aftet that we have $$$k$$$ vertices left, lets run an $$$O(k^2)$$$ algoritm to find the connected components of the complement.

        Let's analyze the complexity. The vertex with the smallest degree has degree $$$O(m / n)$$$, so complexity is $$$O(m^2 / n^2) = O(\frac{m}{n^2} m) = O(m)$$$ because $$$m \le n^2$$$.

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

          Thanks for adding something new to my knowledge!! It worked very well.

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

          I am 2 years too late. But, does the same approach work if we don't start with the vertex having a minimum degree? It's just that time complexity will increase, right?

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

          I used this approach but my code will probably get TLE because after I picked the node with the smallest degree I am naively checking for each of its neighbours (in the original graph) if they have a connection with one if its neighbours (in the complement graph). If they don't have this means the new node will be in the same component as the first one. I think this is O(n*m). Any idea how to speed it up?

          My code: https://codeforces.net/contest/920/submission/176205179

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

          I am having a hard time understanding this algorithm. Can you please explain what do you mean by "squeeze these into a single vertex" and "After that we have k vertices left" ?

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

Basic idea is to maintain a global set of unvisited vertices. Do a dfs. When you're at a particular vertex u, you can iterate through all the unvisited vertices. And if there's an edge in the original graph, just skip that vertex. Why is this not n^2? Because the number of skips would be equal to the number of edges present in the original graph and and you visit each vertex atmost once. Complexity : O((n+m)logn) because of set.

You can see my submission for 0-1 MST for more clarity : Link

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

    That was amazing

    Thanks for helping out!!

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

    Hi!

    I have one doubt. Why are you using the upper bound function to traverse through the unvisited vertices? Why not simply apply loop on remaining vertices in the unvisited set?

    TIA

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

      So if we apply the loop on the unvisited vertices, there's a bit of problem that might occur. Since we're also removing the vertices from the global set too, to avoid any iterator error, I use upper_bound. Seems more safe to me. The iterator don't behave properly if an element is erased, it seems.

      The same thing implemented using loop : Link. Gives runtime on samples.

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

        Thanks for replying. I checked that runtime error is coming but wanted to what is going wrong and why the problem gets solved on using upper bound

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

    I tried your approach for 920E but it gives me TLE. here's my submission:

    244650704

    I have no idea what am I missing.

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

      My apologies for disturbance, but I found the issue. It was me using upper_bound instead of .upper_bound.

      → Reply