Minimum Connection Cost

Difficulty: Medium · Topic: Minimum spanning trees

Given n nodes labeled 0..n-1 and weighted undirected edges [u, v, w], return the total weight of a minimum spanning tree. If the graph is disconnected, return -1.

Examples

minimum_connection_cost(4, [[0,1,1],[0,2,4],[1,2,2],[1,3,6],[2,3,3]])
→ 6

Use weights 1, 2, and 3.

minimum_connection_cost(3, [[0,1,5]])
→ -1

Node 2 is disconnected.

Target complexity: time O(E log E), space O(V)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.