Time and Space Complexity

Time Complexity:

• Sorting the E edges is O(E log E); each union-find operation is nearly O(1) with path compression, so classic Kruskal is O(E log E). The min-selection version we build here is O(E²), which is fine for small graphs.

Space Complexity:

• O(V) for the parent array (plus the input edges).

Summary:

• Kruskal grows an MST by adding the cheapest cycle-free edge at each step, using union-find to test for cycles.
• All MSTs share the same total weight, so the answer is unique.