Hello, I was solving this Leetcode problem yesterday.

I'll rewrite the problem statement once again for convenience:

It's a cool problem. I would suggest to try solving by your own.

Onto the main part now.

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 DSU 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.