Build a minimum spanning tree by taking edges cheapest first, skipping any edge whose ends are already connected (it would close a cycle). A union–find structure answers “already connected?” almost instantly.
- Average time
- O(E log E)
- Space
- O(V + E)
Build a minimum spanning tree by taking edges cheapest first, skipping any edge whose ends are already connected (it would close a cycle). A union–find structure answers “already connected?” almost instantly.