The connected components of an undirected graph are determined in the
EREW model with p processors, using a parallel extension of the ''spar
sification'' technique. A previous algorithm due to Kruskal et al. is
optimal for p less-than-or-equal-to ml/(2+epsilon) < n/2. We show that
our algorithm is work-optimal for an extended range of values. Using
the ''sparsification'' tree data structure we provide also a dynamic a
lgorithm to maintain the connectivity property of a graph as edges are
inserted and deleted.