Friend Circles


@sean46 It depends of your union/find implementation.A efficient one with rank and path compression, will give you O(1) on average.

I think for UnionFind approach, the complexity could be O(n^2) if path compression is used. UnionFind complexity with path compression is O(m), which m is operations (either union/find); in this case, since m[i][j] = m[j][i], the union operation is at most n*(n1)/2, therefore it is O(n^2)