### jarvis307's blog

By jarvis307, history, 22 months ago,

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

• +3

 » 22 months ago, # |   -13 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 edgeprim: node is center kruskal: edge is centerso, 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!
•  » » 22 months ago, # ^ |   0 You may still have to look at way too many edges with Prim. These problems aren't such straightforward applications of MST algorithms.
•  » » » 22 months ago, # ^ |   0 Can you please share your approach if you have some!!TIA!!
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +11 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$.
•  » » » » » 22 months ago, # ^ |   0 Thanks for adding something new to my knowledge!! It worked very well.
 » 22 months ago, # | ← Rev. 2 →   +19 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
•  » » 22 months ago, # ^ |   +8 That was amazingThanks for helping out!!
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » 22 months ago, # ^ |   0 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