Problem Statement

You are given an undirected connected graph with n nodes labeled from 0 to n - 1 and a 2D integer array edges where edges[i] = [ui, vi, wi] denotes an undirected edge between node ui and node vi with weight wi, and an integer k.

You are allowed to remove any number of edges from the graph such that the resulting graph has at most k connected components.

The cost of a component is defined as the maximum edge weight in that component. If a component has no edges, its cost is 0.

Return the minimum possible value of the maximum cost among all components after such removals.

Test Cases

Example 1:

Input: n = 5, edges = [[0,1,4],[1,2,3],[1,3,2],[3,4,6]], k = 2

Output: 4

Explanation:

Remove the edge between nodes 3 and 4 (weight 6).
The resulting components have costs of 0 and 4, so the overall maximum cost is 4.
Example 2:

Input: n = 4, edges = [[0,1,5],[1,2,5],[2,3,5]], k = 1

Output: 5

Explanation:

No edge can be removed, since allowing only one component (k = 1) requires the graph to stay fully connected.
That single component’s cost equals its largest edge weight, which is 5.

Constraints:

1 <= n <= 5 * 10^4
0 <= edges.length <= 10^5
edges[i].length == 3
0 <= ui, vi < n
1 <= wi <= 10^6
1 <= k <= n
The input graph is connected.

Intuition

From the problem statement, we need to find theminimum possible value of the maximum edge weight such that, if we remove all edges with weight greater than this value, the graph splits intoat mostk connected components.

This hints at abinary search strategy on the edge weights, because we’re looking for theminimum value satisfying a condition.

The concept ofconnected components immediately suggests usingUnion Find (Disjoint Set Union - DSU) orDFS/BFS. Since DSU is more efficient for repeated connectivity queries, it's the preferred choice here.

So the idea is:

🔍Use binary search on the edge weight — and for each weightW, check if the number of connected components formed using only edges ≤W is ≤k.

Approach

1. Identify themaximum edge weight in the graph — this is the upper bound for binary search.
2. Performbinary search in the range[0, maxWeight]:
   • For each midpoint weightW, consider only edges with weight ≤W.
   • UseUnion Find to connect nodes using only those edges.
   • Count the number of connected components formed.
3. If the number of components is ≤k, thenW is avalid candidate, but try to find a smaller one (moveright = mid - 1).
4. If more thank components are formed, thenW istoo small (moveleft = mid + 1).
5. Finally, return thesmallest weight that satisfies the condition.

Complexity

Time Complexity:

O(log(maxWeight) * E * α(N))

• Binary Search:O(log(maxWeight))
• Each check: Union-Find over allE edges →O(E * α(N)), whereα(N) is the inverse Ackermann function (nearly constant time).

Space Complexity:

O(N) for Union-Find structures

Code

classSolution{publicintminCost(intn,int[][]edges,intk){if(edges==null||n<=0||k<0){return0;}intmaxWeight=0;for(int[]edge:edges){maxWeight=Math.max(maxWeight,edge[2]);}returnfindMinCost(edges,k,n,maxWeight);}publicintfindMinCost(int[][]edges,intk,intn,intmaxWeight){intlow=0;inthigh=maxWeight;intanswer=-1;while(low<=high){intmiddle=low+(high-low)/2;if(isGraphHaveKComponent(edges,k,middle,n)){answer=middle;high=middle-1;}else{low=middle+1;}}returnanswer;}privatebooleanisGraphHaveKComponent(int[][]edges,intk,intcurrentMaxWeight,intn){UnionFindunionFind=newUnionFind(n);for(int[]edge:edges){intnode1=edge[0];intnode2=edge[1];intweight=edge[2];if(weight<=currentMaxWeight){unionFind.union(node1,node2);}}returnunionFind.getComponentCount()<=k;}}classUnionFind{int[]rank;int[]parent;intcomponentCount;publicUnionFind(intn){if(n<=0){thrownewIllegalArgumentException("N cannot be less or equal to 0");}componentCount=n;rank=newint[n];parent=newint[n];for(intnode=0;node<n;node++){rank[node]=1;parent[node]=node;}}publicintfindParent(intnode){if(node!=parent[node]){parent[node]=findParent(parent[node]);}returnparent[node];}publicvoidunion(intnode1,intnode2){intparentNode1=findParent(node1);intparentNode2=findParent(node2);if(parentNode1==parentNode2){return;}if(rank[parentNode1]<rank[parentNode2]){parent[parentNode1]=parentNode2;rank[parentNode2]+=rank[parentNode1];}else{parent[parentNode2]=parentNode1;rank[parentNode1]+=rank[parentNode2];}componentCount--;}publicbooleanisConnectedComponent(intnode1,intnode2){returnfindParent(node1)==findParent(node2);}publicintgetComponentCount(){returncomponentCount;}}