Union Find
If we regard a person as a node (or element), a friend circle as a connected component (or set), the problem becomes to find the total number of connected compo
If we regard a person as a `node` (or `element`), a friend circle as a `connected component` (or `set`), the problem becomes to find the total number of connected components in a graph.\n****\n```\nclass Solution {\n    public int findCircleNum(int[][] M) {\n        UF uf = new UF(M.length);\n        \n        for (int i = 0; i < M.length - 1; i++) {\n            for (int j = i + 1; j < M.length; j++) {\n                if (M[i][j] == 1) {\n                    uf.union(i, j);\n                }\n            }\n        }\n        \n        return uf.count();\n    }\n    \n    class UF{\n        int[] parent;\n        public UF(int n) {\n            parent = new int[n];\n            for (int i = 0; i < n; i++)\n                parent[i] = i;\n        }\n        void union(int x, int y) {\n            int rx = find(x);\n            int ry = find(y);\n            if (rx != ry) {\n                parent[rx] = ry;\n            }\n        };\n        int find(int x) {\n            if (parent[x] == x) {\n                return x;\n            }\n            return parent[x] = find(parent[x]); // path compression\n        }\n        int count() {\n            // Count parent[x] = x\n            int cnt = 0;\n            for (int i = 0; i < parent.length; i++)\n                if (parent[i] == i) {\n                    cnt++;\n                }\n            return cnt;\n        }\n    }\n}\n```\n
[]