Simple Implementation: DFS

All the work done in CONNECTED. Let JOIN just add the given edge to a set of edges. Now, can use depth-first-search to test connectivity when we need to. Basically, if we start at u and can reach v, they are connected. If not, not.

That gives us: $\Theta(\vert V\vert+\vert E\vert) \vert E\vert = O(\vert E\vert^2)$ for all the calls to CONNECTED and JOIN. This dominates that $O(\vert E\vert \log \vert E\vert)$ for sorting the edges, giving O(|E|²) running time.

Explanation: for each edge that we consider adding, we do a depth-first search over edges to see if the endpoints are already connected.