MST With Mandatory and Forbidden Edges

Given a weighted undirected graph, some edges must be included in the spanning tree and some edges must be excluded. Return the minimum total cost of a spanning tree that respects both constraints, or -1 if no such tree exists. Pattern focus: Minimum Spanning Tree. This is a constrained MST variant that combines forced unions with forbidden choices.

Input Format

n = number of vertices, edges = weighted undirected edges [u, v, w], mandatoryEdges = indices that must be included, forbiddenEdges = indices that cannot be used

Output Format

minimum MST cost respecting the constraints, or -1 if impossible

Constraints

  • 1 <= n <= 10^5
  • 1 <= edges.length <= 2 * 10^5
  • 0 <= mandatoryEdges.length, forbiddenEdges.length <= edges.length

Examples

Example 1:

Input:

n = 4
edges = [[1,2,1],[2,3,2],[3,4,3],[1,4,4],[1,3,5]]
mandatoryEdges = [0]
forbiddenEdges = [3]

Output:

6

Explanation:

The mandatory edge 1-2 is included, and the best remaining edges give total cost 6.

Example 2:

Input:

n = 4
edges = [[1,2,1],[2,3,2],[3,4,3],[1,4,4]]
mandatoryEdges = [3]
forbiddenEdges = [2]

Output:

7

Explanation:

Edge 1-4 must be included, and the cheapest compatible tree costs 7.

Example 3:

Input:

n = 3
edges = [[1,2,1],[2,3,1],[1,3,1]]
mandatoryEdges = [0,1]
forbiddenEdges = []

Output:

2

Explanation:

The mandatory edges already connect all vertices and form a valid tree.

Loading...
MST With Mandatory and Forbidden Edges