We don't need to call the find method every time for both row and column indexes (i and j). Instead, we only need to call the find method only once for row index (i) before the going to the loop of column index (j). But in this way, we need to update the find result of i every time after the union. To do this, we can let the union method to return the final root to update the i value.

I also write the union find to weighted and path compression union find. The time complexity is O(n^2*logn).

public int findCircleNum(int[][] M) {
int m = M.length;
if(m==0) return 0;
int[] roots = new int[m];
int[] sc = new int[m];
for(int i=0;i<m;i++) roots[i]=i;
Arrays.fill(sc,1);
int count=m;
for(int i=0;i<m;i++)
{
int x= find(roots,i);
for(int j=i+1;j<m;j++)
{
if(M[i][j]!=1) continue;
int y= find(roots,j);
if(x!=y)
{
count--;
x=union(roots,x,y,sc);
}
}
}
return count;
}
public int find(int[] roots, int i) {
while(roots[i]!=i)
{
roots[i]=roots[roots[i]];//path compression
i=roots[i];
}
return i;
}
public int union(int[] roots, int x, int y, int[] sc) {
if(sc[x]>sc[y])//weighted union
{
roots[y]=x;
sc[x]+=sc[y];
return x;
}
else
{
roots[x]=y;
sc[y]+=sc[x];
return y;
}
}