FriendCircles2.java

public class FriendCircles {
    private int count;

    public int findCircleNum(int[][] M) {
        count = M.length;
        int len = M.length;

        int[] circles = new int[len];
        int[] rank = new int[len];
        for (int i = 0; i < len; i++) {
            circles[i] = i;
        }

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (M[i][j] == 1) {
                    union(circles, rank, i, j);
                }
            }
        }
        return count;
    }

    public void union(int[] circles, int[] rank, int i, int j) {
        int root1 = findCircle(circles, i);
        int root2 = findCircle(circles, j);
        if (root1 == root2) return;

        if (rank[root1] < rank[root2]) {
            circles[root1] = root2;
        } else if (rank[root1] > rank[root2]) {
            circles[root2] = root1;
        } else {
            circles[root1] = root2;
            rank[root1] += 1;
        }
        count--;
    }

    public int findCircle(int[] circles, int i) {
        while (circles[i] != i) {
            // path compression by halving
            circles[i] = circles[circles[i]];
            i = circles[i];
        }
        return i;
    }
}