Better Implementation

We can make CONNECTED run fast by precomputing which nodes are connected to which other nodes. Could do this with a $\vert V\vert\times\vert V\vert$ array, but this is more than is needed. Can do this just an array of size |V|. How?

Now, all the work will be in JOIN to update who is connected to whom.

So, what ought to happen when join to nodes?

We could relabel all the nodes, but this could be expensive. What's the cheap way to make them the same color?

But, to do this, we'll need to be able to quickly run through all nodes of the same color. How can we do this?