Algorithm for clustering points in $\mathbb{R}^2$ based on pairwise distance (percolation graphs)
The following algorithm does unfortunately does not allow you to get the $n^2$ factor out (see comment below).

Superimpose an $r/\sqrt 2$-by-$r/\sqrt 2$ grid on the unit square: notice that every point within the same grid cell is automatically within the same cluster.  Also notice that there can be at most $n$ grid cells containing one or more points; these are the only grid cells we need to consider from this point on.


Map each point to its grid cell.
For each grid cell, throw all contained points into the same cluster.
For each pair of neighbouring grid cells $P$, $Q$ (each grid cell, apart from those at edges and corners, has 8 such neighbours), determine the closest pair of points $p, q$ having $p \in P$ and $q \in Q$ using this $O(n\log n)$ algorithm.  If $d(p, q) &lt; r$ then combine $C(P)$ and $C(Q)$, otherwise not.


You can use a union/find disjoint set data structure to maintain the clusters in close-to-linear time, just as per the Kruskal algorithm.