Kruskal's Algorithm
MST & Disjoint Set DSA practice problem on Onlearn.
Difficulty: hard.
Topics: How to find the sum of weights of edges in the Minimum Spanning Tree (MST) of a weighted, undirected, and connected graph using Kruskal's algorithm with Disjoint Set?, Graph, Weighted Graph, Undirected Graph, Edge, Spanning Tree, Minimum Spanning Tree, Kruskal's Algorithm, Disjoint Set Union, Union by Size, Path Compression, Sorting, Time Complexity, Space Complexity, kruskal's algorithm, graph representation, union-find, graph algorithms, minimum spanning tree, cycle detection, time complexity analysis, DSU Applications, Custom Sorting Criteria.
Problem Statement Given a weighted, undirected, and connected graph of V vertices and E edges, find the sum of weights of the edges of the Minimum Spanning Tree (MST). Input Format: The input consists of: An integer V, representing the number of vertices. A list of edges, where each edge is represented as a triplet {u, v, w}, indicating an edge between vertex u and vertex v with weight w. Output Format: The output should be a single integer representing the sum of weights of the edges of the Minimum Spanning Tree. Sample Test Cases: Example 1: Input: V = 5, edges = { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {4, 2, 7}} Output: 16 Explanation: The minimum spanning tree for the given graph would include edges (0, 1), (0, 3), (1, 2), and (1, 4). Sum of weights = 2 + 6 + 3 + 5 = 16. Example 2: Input: V = 5, edges = { {0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}} Output: 5 Explanation: The minimum spanning tree would include edges (0, 2), (1, 2), (2, 3), and (3, 4). Sum of weights = 1 + 1 + 2 + 1 = 5.