  Identifying the connected components of a graph, apart from being a
fundamental problem with countless applications, is a key primitive for many
other algorithms. In this paper, we consider this problem in parallel settings.
Particularly, we focus on the Massively Parallel Computations (MPC) model,
which is the standard theoretical model for modern parallel frameworks such as
MapReduce, Hadoop, or Spark. We consider the truly sublinear regime of MPC for
graph problems where the space per machine is $n^\delta$ for some desirably
small constant $\delta \in (0, 1)$.
  We present an algorithm that for graphs with diameter $D$ in the wide range
$[\log^{\epsilon} n, n]$, takes $O(\log D)$ rounds to identify the connected
components and takes $O(\log \log n)$ rounds for all other graphs. The
algorithm is randomized, succeeds with high probability, does not require prior
knowledge of $D$, and uses an optimal total space of $O(m)$. We complement this
by showing a conditional lower-bound based on the widely believed TwoCycle
conjecture that $\Omega(\log D)$ rounds are indeed necessary in this setting.
  Studying parallel connectivity algorithms received a resurgence of interest
after the pioneering work of Andoni et al. [FOCS 2018] who presented an
algorithm with $O(\log D \cdot \log \log n)$ round-complexity. Our algorithm
improves this result for the whole range of values of $D$ and almost settles
the problem due to the conditional lower-bound.
  Additionally, we show that with minimal adjustments, our algorithm can also
be implemented in a variant of the (CRCW) PRAM in asymptotically the same
number of rounds.
