Finding connected components without building the graph first
I have an idea for the algorithm that's slightly better than a simple dfs based on the fact that the relationship is transitive.
From transitivity follows that $a \sim b \land b \sim c \Rightarrow a \sim c$. For our undirected graph this implies that every node in a connected component is connected to every other node. This yields following simple algorithm:
component = 1
mark = array of size n; initialized with 0
for i = 1 to n:
  if mark[i] == 0:
    mark[i] = component
    for j = i+1 to n:
      if i != j and mark[j] == 0 and c(X[i],X[j]):
        mark[j] = component
    component += 1

$mark$ now assigns every node a component.
The runtime of the algo is $O(cn)$ where $c$ is the number of components.
This would usually considerably faster than a dfs.
Notice in the worst case every node is its own component leading to $O(n^2)$.
But if this even occurs depends on the properties of your $c(x,y)$ function.
EDIT: The algorithm doesn't work since c(x,y) isn't transitive. My bad.