Complete analysis and solutions for this question, DFS/BFS/UnionFind.
Solution1: DFS or BFS\n\nWe can reduce abstract this problem into finding connected groups in a undirected graph represented as an adjacency matrix.  \n\nSince 
# Solution1: DFS or BFS\n\nWe can reduce abstract this problem into finding __connected groups__ in a undirected graph represented as an __adjacency matrix__.  \n\nSince we want to treat the input `M` as a adjacency matrix, we treate each row from `0` to `n - 1` as `n` nodes. Hence we use a `boolean[]` to store the visited status.  \n\nTherefore, a normal graph traversal algorithms can be utilized to find the number of connected gropus in this undirected graph.  \n\n## DFS solution:\n\nSince the input matrix `M` is `n*n` in size  \nTime complexity: `O(n^2)`   \n\nSpace complexity: `O(n)`  \n\n```Java\nclass Solution {\n    public int findCircleNum(int[][] M) {\n        if (M == null || M.length == 0 || M[0].length == 0) return 0;\n        boolean[] visited = new boolean[M.length];\n        int count = 0;\n        for (int i = 0; i < M.length; i++) {\n            if (!visited[i]) {\n                count++;\n                dfs(M, i, visited);\n            }\n        }\n        \n        return count;\n    }\n    \n    private void dfs(int[][] M, int i, boolean[] visited) {\n        for (int j = 0; j < M[i].length; j++) {\n            if (M[i][j] == 1 && !visited[j]) {\n                visited[j] = true;\n                dfs(M, j, visited);\n            }\n        }\n    }\n}\n```\n\n## BFS solution: \n\nThe same idea, but used a `Queue` to perform the BFS process. \n\nTime complexity: `O(n^2)`\n\nSpace complexity: `O(n)`\n\n```Java\nclass Solution {\n    public int findCircleNum(int[][] M) {\n        if (M == null || M.length == 0 || M[0].length == 0) return 0;\n        boolean[] visited = new boolean[M.length];\n        int count = 0;\n        for (int i = 0; i < M.length; i++) {\n            if (!visited[i]) {\n                bfs(M, i, visited);\n                count++;\n            }\n        }\n        \n        return count;\n    }\n    \n    private void bfs(int[][] M, int i, boolean[] visited) {\n        Queue<Integer> queue = new LinkedList<>();\n        queue.offer(i);\n        visited[i] = true;\n        while (!queue.isEmpty()) {\n            int curr = queue.poll();\n            for (int j = 0; j < M[curr].length; j++) {\n                if (M[curr][j] == 1 && !visited[j]) {\n                    queue.offer(j);\n                    visited[j] = true;\n                }\n            }\n        }\n    }\n}\n```\n\n# Solution2: Union-find\n\nSince we've already reduced the question into a connectivity problem, __union-find__ algorithm seems to be appliable to this question, for it's suitable to be used for dynamic connectivity problem.  \n\nFor this question, specifically, we still treat the input `M` as a __adjacency matrix__. And row index `0` to `n-1` as `n` nodes. We check each edge (`M[i][j]`) between each node pairs, and union `i` and `j`. After we `union`ed each edge, we check the number of roots, i.e. where `i == id[i]`, and return it as the number of connected components. \n\nNote that we have 2 optimization for the `union-find` algorithm:   \n1. During the `union()` process, we check the size of each connected component and union the smaller one to the greater one. This is called __weighed union__ and can flatten the depth of the connected component and improve the efficiency of the `union-find` algorithm.  \n2. During the `findRoot()` process, we used path compression to flatten the depth of the connected component, also improved the efficiency of the algorithm.  \n\nBy utilizing this 2 improvements, the time complexity of calling `union()` for M times is `O(n + Mlg*n)`, which can be viewed as `O(n)`, because `lg*n` can be viewed as a constant.  \n\n```Java\nclass Solution {\n    // weighed quick union with path compression\n    public int findCircleNum(int[][] M) {\n        int[] size = new int[M.length];\n        int[] id = new int[M.length];\n        for (int i = 0; i < M.length; i++) {\n            id[i] = i;\n            size[i] = 1;\n        }\n        for (int i = 0; i < M.length; i++) {\n            for (int j = 0; j < M[i].length; j++) {\n                if (M[i][j] == 1) {\n                    union(id, size, i, j);\n                }\n            }\n        }\n        \n        int count = 0;\n        for (int i = 0; i < id.length; i++) {\n            if (i == id[i]) {\n                count++;\n            }\n        }\n        \n        return count;\n    }\n    \n    private void union(int[] id, int[] size, int i, int j) {\n        int rootI = findRoot(id, i);\n        int rootJ = findRoot(id, j);\n        \n        // weighed quick union\n        if (size[rootI] >= size[rootJ]) {\n            id[rootJ] = rootI;\n            size[rootI] += size[rootJ];\n        } else {\n            id[rootI] = rootJ;\n            size[rootJ] += size[rootI];\n        }\n    }\n    \n    private int findRoot(int[] id, int curr) {\n        while (curr != id[curr]) {\n            // path compression\n            id[curr] = id[id[curr]];\n            curr = id[curr];\n        }\n        return curr;\n    }\n}\n```
[]