| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3741 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3442 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 2 | atcoder_official | 162 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | nor | 150 |
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
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!
You may still have to look at way too many edges with Prim. These problems aren't such straightforward applications of MST algorithms.
Can you please share your approach if you have some!!
TIA!!
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$$$.
Thanks for adding something new to my knowledge!! It worked very well.
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?
Yes, exactly.
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
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" ?
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
That was amazing
Thanks for helping out!!
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
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.
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
I tried your approach for 920E but it gives me TLE. here's my submission:
244650704
I have no idea what am I missing.
My apologies for disturbance, but I found the issue. It was me using upper_bound instead of .upper_bound.