Java solution, Union Find
This is a typical Union Find problem. I abstracted it as a standalone class. Remember the template, you will be able to use it later.\n\npublic class Solution {
This is a typical ```Union Find``` problem. I abstracted it as a standalone class. Remember the template, you will be able to use it later.\n```\npublic class Solution {\n    class UnionFind {\n        private int count = 0;\n        private int[] parent, rank;\n        \n        public UnionFind(int n) {\n            count = n;\n            parent = new int[n];\n            rank = new int[n];\n            for (int i = 0; i < n; i++) {\n                parent[i] = i;\n            }\n        }\n        \n        public int find(int p) {\n        \twhile (p != parent[p]) {\n                parent[p] = parent[parent[p]];    // path compression by halving\n                p = parent[p];\n            }\n            return p;\n        }\n        \n        public void union(int p, int q) {\n            int rootP = find(p);\n            int rootQ = find(q);\n            if (rootP == rootQ) return;\n            if (rank[rootQ] > rank[rootP]) {\n                parent[rootP] = rootQ;\n            }\n            else {\n                parent[rootQ] = rootP;\n                if (rank[rootP] == rank[rootQ]) {\n                    rank[rootP]++;\n                }\n            }\n            count--;\n        }\n        \n        public int count() {\n            return count;\n        }\n    }\n    \n    public int findCircleNum(int[][] M) {\n        int n = M.length;\n        UnionFind uf = new UnionFind(n);\n        for (int i = 0; i < n - 1; i++) {\n            for (int j = i + 1; j < n; j++) {\n                if (M[i][j] == 1) uf.union(i, j);\n            }\n        }\n        return uf.count();\n    }\n}\n```
[]