DSA interview question

MST Basics: Is This Edge Set a Minimum Spanning Tree?

Easy · Data structures · Topics: graph, mst, theory

The problem

A telecom planner must connect all towns with cable. Any valid plan is a spanning tree: it connects all V towns using exactly V − 1 links and no loops. The cheapest such plan is a minimum spanning tree (MST). A contractor submits a set of links. Verify that it's (1) a spanning tree and (2) of minimum total cost, by comparing its cost with an MST computed by Kruskal's algorithm. This covers the core MST facts: V − 1 edges, no cycles, connected, and minimum total weight.

Example: 4 towns, links 0-1 (1), 1-2 (2), 2-3 (1), 0-3 (4), 0-2 (3). The proposal 0-1, 1-2, 2-3 costs 4 → true.

Function signature

bool isMST(int V, const vector<array<int, 3>>& edges, const vector<array<int, 3>>& candidate);
// candidate edges come from the (connected) graph

Test cases

Input: candidate (graph: 4 towns, `0-1:1, 1-2:2, 2-3:1, 0-3:4, 0-2:3`)	Output	Explanation
`[[0,1,1],[1,2,2],[2,3,1]]`	`true`	A spanning tree of weight 4, which is minimal
`[[0,1,1],[2,3,1],[0,2,3]]`	`false`	A spanning tree, but weight 5
`[[0,1,1],[1,2,2]]`	`false`	Town 3 isn't connected
`[[0,1,1],[1,2,2],[2,3,1],[0,3,4]]`	`false`	4 edges means a cycle
`V = 1`, no edges, candidate `[]`	`true`	A single town needs no links

(Confirm: the graph is connected and undirected; the candidate must use exactly V − 1 edges from the graph.)

How interviewers phrase it

"Explain what a minimum spanning tree is, and check whether a given set of edges forms one."

Clarifying questions to ask

Is the graph connected? (Yes; otherwise the concept is a minimum spanning forest.)
Are edge weights distinct? (Not necessarily, so the MST may not be unique, but its weight is.)
Are the candidate edges guaranteed to come from the graph? (Assume yes.)

Follow-ups to expect

"Key MST facts?"
"Cut property?"
"Cycle property?"
"How do you verify a spanning tree quickly?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview