Graph Theory37 sections · 1633 units
Open in Course

Core Idea - Kruskal is Perfect Here

(Sort edges, union components)

Kruskal is perfect for this problem because you can easily count how many edges you added. If you added n1n-1 edges, the graph is connected and you have the MST. Otherwise, it is impossible. The algorithm handles both cases without special logic. Check the edge count at the end.

No extra work needed. This is simpler than other connectivity checks. Use Union-Find to detect cycles and build the MST efficiently.