Kruskal with Union-Find

Union-Find (Disjoint Set Union) tracks which nodes are connected. Each node starts in its own component. When you add an edge, you merge two components. Before adding edge $(u, v)$, check if $u$ and $v$ are already in the same component using find(u) == find(v).

If yes, skip the edge (it would create a cycle). If no, add the edge and merge components with union(u, v). This lets Kruskal detect cycles in nearly constant time per edge.