朋友圈

解法一：深度优先遍历DFS（递归）

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0) {
            return 0;
        }
        int ret = 0;
        boolean[] mark = new boolean[M.length];
        for (int i = 0; i < M.length; i++) {
            if (mark[i]) {
                continue;
            }
            ret++;
            find(M, mark, i);
        }
        return ret;
    }

    private void find(int[][] M, boolean[] mark, int x) {
        mark[x] = true;
        for (int i = 0; i < M.length; i++) {
            if (M[x][i] == 1 && mark[i] == false) {
                find(M, mark, i);
            }
        }
    }

解法二：广度优先遍历BFS（队列）

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0) {
            return 0;
        }
        int ret = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] mark = new boolean[M.length];
        for (int i = 0; i < M.length; i++) {
            if (mark[i]) {
                continue;
            }
            queue.offer(i);
            while (!queue.isEmpty()) {
                int x = queue.remove();
                mark[x] = true;
                for (int j = 0; j < M.length; j++) {
                    if (M[x][j] == 1 && mark[j] == false) {
                        queue.offer(j);
                    }
                }
            }
            ret++;
        }
        return ret;
    }

解法三：并查集

   public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0) {
            return 0;
        }
        int len = M.length;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = i;
        }

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

    private void union(int[] set, int i, int j) {
        set[find(set, j)] = find(set, i);
    }

    private int find(int[] set, int i) {
        int origin = i;
        while (i != set[i]) {
            i = set[i];
        }
        return i;
    }

使用了一种合适的数据结构，避免了繁琐的编码。
关于数据结构，你需要明白：

1. 选择：根据数据和情景，选择合适的数据结构。
2. 构造：初始化
3. 使用：熟悉API

题目：朋友圈
参考：八连块问题
数据结构：并查集