Hello, I was solving this Leetcode problem yesterday.
I'll rewrite the problem statement once again for convenience:
I would suggest to try solving by your own before reading further.
I came across this nice solution where you first sort the edges, in increasing order of their edge weights.
This is followed by greedily picking edges from smallest to largest and using Disjoint Set/Union Find to keep count of connected components so far.
While reading through the solution, I came up with an idea that works in reverse:
Build the entire graph using the edge information. Initially it is guaranteed to be 1 connected component.
Sort the edges in decreasing order of their edge weights (large to small).
Greedily remove the edges (largest to smallest) and for every edge removed edge, check if connected components reaches upto $$$k$$$ or not.
The last step "kind of" resembles the operation that has the opposite effect than what the Disjoint Set/Union Find Data Structure does. You perform the opposite of Union and then have to check if the components are disconnected or not.
This is probably a harder way to approach this problem, but I wanted to give it a try for better understanding.
- How do I approach this if I wanted to follow the steps that I wrote?.
- Is there a way to solve this problem efficiently?
- Is there a data structure that is able to calculate connected components and can support edge deletions for given constraints?.
