Abstract Finding the connected components of an undirected graph G=( V, E) on n=| V| vertices and m=| E| edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs in O(log 2 n) time using n 2/log 2 nprocessors. For the CRCW PRAM model, in which concurrent writing is permitted, the best known algorithm runs in O(log n) time using slightly more than ( n+ m)/log nprocessors. Simulating this algorithm on the weaker CREW model increases its running time to O(log 2 n). We present here a simple algorithm that runs in O(log 3/2 n) time using n+ mCREW processors. Finding an o(log 2 n) parallel connectivity algorithm for this model was an open problem for many years.