Can someone please explain what this problem was asking for?
“The final result will be guaranteed to have no roads(since all roads must be destroyed).”
then the result of the example is [1, 1, 2, 3, 4], which is confusing…
The ith element in the output corresponds to the number of connected components after the ith edge/road has been removed. Moreover, breaks exactly removes one edge from the graph at a time until there are no more edges/roads, meaning that after removing the last edge/road in breaks, the graph is without any edges, meaning n connected components.
It starts at 1 because all the cities are still connected therefore there is 1 city cluster (which is a set). We break roads [1,2] but all the cities are still connected therefore we still have 1 city cluster. When we break [2,3] there is still 1 city cluster since they are all connected via city 4. Once we break roads [3,4], city 3 is isolated as no roads lead to it therefore it is its own city cluster and we now have 2 city clusters.
nice problem!
What is the key observation that you must go backwards instead of forwards to slowly create the graph?
Can you please explain why we need to merge the edges in the reverse order? Why do we reverse sort the input?