FriendCircles1.java

package leetcode;


public class FriendCircles {
    private int count;

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

        int[] circles = 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, i, j);
                }
            }
        }
        return count;
    }

    public void union(int[] circles, int i, int j) {
        int root1 = findCircle(circles, i);
        int root2 = findCircle(circles, j);
        if (root1 == root2) return;
        circles[root2] = root1;
        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;
    }
}