  Given a partition of an n element set into equivalence classes, we consider
time-space tradeoffs for representing it to support the query that asks whether
two given elements are in the same equivalence class. This has various
applications including for testing whether two vertices are in the same
component in an undirected graph or in the same strongly connected component in
a directed graph.
  We consider the problem in several models.
  -- Concerning labeling schemes where we assign labels to elements and the
query is to be answered just by examining the labels of the queried elements
(without any extra space): if each vertex is required to have a unique label,
then we show that a label space of (\sum_{i=1}^n \lfloor {n \over i} \rfloor)
is necessary and sufficient. In other words, \lg n + \lg \lg n + O(1) bits of
space are necessary and sufficient for representing each of the labels. This
slightly strengthens the known lower bound and is in contrast to the known
necessary and sufficient bound of \lceil \lg n \rceil for the label length, if
each vertex need not get a unique label.
  --Concerning succinct data structures for the problem when the n elements are
to be uniquely assigned labels from label set {1, 2, ...n}, we first show that
\Theta(\sqrt n) bits are necessary and sufficient to represent the equivalence
class information. This space includes the space for implicitly encoding the
vertex labels. We can support the query in such a structure in O(\lg n) time in
the standard word RAM model. We then develop structures resulting in one where
the queries can be supported in constant time using O({\sqrt n} \lg n) bits of
space. We also develop space efficient structures where union operation along
with the equivalence query can be answered fast.
