Umbristan | Reverse Union Find - Advanced Data Structures / Disjoint Set Union | Union Find
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.
Guys no offense, you really need a native English speaker to write this problem description. Current text is confusing and cannot be understood without the example that follows.
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?