Prim's Algorithm
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding the Minimum Spanning Tree (MST) and its total edge weight in a weighted, undirected, connected graph, Minimum Spanning Tree, Prim's Algorithm, Graph, Weighted Graph, Undirected Graph, Heap/Priority Queue, Greedy Algorithm, Time Complexity, Space Complexity, Adjacency List, Arrays, Node, Edge, graph representation, priority queue, greedy algorithm, graph traversal, minimum spanning tree, prim's algorithm, time complexity analysis.
Minimum Spanning Tree Sum Problem Statement Given a weighted, undirected, and connected graph consisting of V vertices and E edges, your task is to find the total sum of weights of the edges that form a Minimum Spanning Tree (MST) of this graph. A Minimum Spanning Tree (MST) is a subgraph that connects all vertices together, without any cycles, and with the minimum possible total edge weight. Input Specification The first line of input contains an integer V, representing the number of vertices. The second line contains an array of edges, where each edge is represented as a triplet {u, v, w}, indicating an edge between vertex u and vertex v with a weight of w. Output Specification Output a single integer representing the sum of the weights of the edges in the Minimum Spanning Tree. Sample Test Cases Sample Input 1 Sample Output 1 Explanation 1 The MST edges are (0, 1), (0, 3), (1, 2), (1, 4), resulting in a total weight of 2 + 6 + 3 + 5 = 16. Sample Input 2 Sample Output 2 Explanation 2 The MST edges are (0, 2), (1, 2), (2, 3), (3, 4), resulting in a total weight of 1 + 1 + 2 + 1 = 5.