Minimum Spanning Tree (MST) Concepts
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Minimum Spanning Tree (MST) and Spanning Tree Concepts, Graph, Weighted Graph, Undirected Graph, Spanning Tree, Minimum Spanning Tree, Greedy Algorithm, Prim's Algorithm, Kruskal's Algorithm, Priority Queue, Disjoint Set Union, Sorting, Time Complexity, Space Complexity, kruskal's algorithm, graph algorithms, minimum spanning tree, graph properties, graph theory, prim's algorithm, Minimum Spanning Tree (MST), MST (Prim's Algorithm), MST (Kruskal's Algorithm).
Problem Statement Given an undirected, weighted graph with N nodes and M edges, find the sum of the edge weights of its Minimum Spanning Tree (MST). A Minimum Spanning Tree (MST) is a subgraph that is a tree and connects all the vertices together, with the minimum possible total edge weight. For a graph with N vertices, an MST will have exactly N 1 edges. Input Specification The first line of input contains two integers, N and M (number of nodes and number of edges, respectively). Each of the next M lines contains three integers u, v, and w, representing an edge between node u and node v with weight w. Nodes are 1 indexed. Output Specification Output a single integer, the sum of the edge weights of the Minimum Spanning Tree. Sample Test Cases Sample Input 1 Sample Output 1