  We study a class of simple algorithms for concurrently computing the
connected components of an $n$-vertex, $m$-edge graph. Our algorithms are easy
to implement in either the COMBINING CRCW PRAM or the MPC computing model. For
two related algorithms in this class, we obtain $\Theta(\lg n)$ step and
$\Theta(m \lg n)$ work bounds. For two others, we obtain $O(\lg^2 n)$ step and
$O(m \lg^2 n)$ work bounds, which are tight for one of them. All our algorithms
are simpler than related algorithms in the literature. We also point out some
gaps and errors in the analysis of previous algorithms. Our results show that
even a basic problem like connected components still has secrets to reveal.
