We present fast and efficient parallel algorithms for finding the connected
components of an undirected graph. These algorithms run on the exclusive-r
ead, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, o
ur randomized algorithm runs in O(log n) time using (m + n(1+epsilon)) = lo
g n EREW processors (for any fixed epsilon > 0). A variant uses (m + n)= lo
g n processors and runs in O(log n log log n) time. A deterministic version
of the algorithm runs in O(log(1.5) n) time using m + n EREW processors.