Simple Union Find and reuse code from Leetcode 924
This is the similar question as Leetcode 924. The code could be reused. \nPlease refer to https://leetcode.com/problems/minimize-malware-spread/discuss/181470/V
This is the similar question as Leetcode 924. The code could be reused. \nPlease refer to https://leetcode.com/problems/minimize-malware-spread/discuss/181470/Very-Simple-Union-Find-O(N2)-no-others\nfor the solution of Leetcode 924\n\nThe key difference here is that the removed point will be completely isolated. So we can create union find for each case that the initial element is removed, and calculate the total infected number in this case, then find the minimum case. If equal, find the smallest index.\n\nSo most of the code in Leetcode 924 could be reused here. The time complexity in this question will be O(m*N*N) compared to O(N*N) in Leetcode 924.\n```\nclass Solution {\n    class UF {\n        int[] parent;\n        int[] size;\n        public UF(int N){\n            parent = new int[N];\n            size = new int[N];\n            for (int i = 0; i < N; i++){\n                parent[i] = i;\n                size[i] = 1;\n            }\n        }\n        public int find(int x){\n            if (parent[x] == x){\n                return x;\n            }\n            return find(parent[x]);\n        }\n        public void union(int x, int y){\n            int rootX = find(x);\n            int rootY = find(y);\n            if (rootX != rootY){\n                parent[rootX] = rootY;\n                size[rootY] += size[rootX];\n            }\n        }\n    }\n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        int N = graph.length;\n        if (initial.length == 1){\n            return initial[0];\n        }\n        int max = N;\n        int res = -1;\n        for (int k = 0; k < initial.length; k++){\n            UF uf = new UF(N);\n            int removePt = initial[k];\n            for (int i = 0; i < N; i++){\n                for (int j = 0; j < N; j++){\n                    if (i == removePt || j == removePt){\n                        continue;\n                    }\n                    if (graph[i][j] == 1){\n                        uf.union(i, j);\n                    }\n                }\n            }\n            int totalInfected = 0;\n            Set<Integer> seen = new HashSet<>();//avoid to add the same group multiple times\n            for (int init : initial){\n                if (init == removePt){\n                    continue;\n                }\n                int root = uf.find(init);\n                int size = uf.size[root];\n                if (!seen.contains(root)){\n                    seen.add(root);\n                    totalInfected += size;\n                }\n            }\n            if (max > totalInfected){\n                res = removePt;\n                max = totalInfected;\n            }else if (totalInfected == max && removePt < res){\n                res = removePt;\n            }\n        }\n        return res;\n    }\n}\n```
[]