jarvis307's blog

By jarvis307, history, 5 weeks 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

»
5 weeks 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!

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      TIA!!

      • »
        »
        »
        »
        5 weeks 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$$$.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That was amazing

    Thanks for helping out!!

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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