Minimum Spanning Tree (Kruskal)

**Problem Statement:** Given the required input arguments, write an efficient algorithm to solve the **Minimum Spanning Tree (Kruskal)** problem. Implement the required logic as specified by standard definitions for this classic algorithmic challenge. **Hint / Expected Approach:** Sort edges + Union-Find **Edge Cases to Consider:** - (1) Single node - (2) Already a tree - (3) Disconnected graph

Examples

Example 1

Input: 4, [[0,1,1],[0,2,4],[1,2,2],[1,3,3],[2,3,5]]

Output: 6

Explanation: Classic MST

Example 2

Input: 2, [[0,1,5]]

Output: 5

Explanation: Single edge

Example 3

Input: 1, []

Output: 0

Explanation: Single node

Constraints

▪2 <= vertices <= 1000
▪0 <= edges <= 5000
▪Avoid infinite cycles during depth traversal

Watch Out For Edge Cases

▪Single node
▪Already a tree
▪Disconnected graph

Frequently Asked At

AmazonGoogleMicrosoftTCS

Back to Arena

medium

Graph