Java 43ms Union Find O(N^3)
for each virus, build a union find map that, all of this virus\' edges will be skipped. \nThen for each node that this skipped virus\' edges connect to, find th
for each virus, build a union find map that, all of this virus\' edges will be skipped. \nThen for each node that this skipped virus\' edges connect to, find the group parent of this node. If this group parent is not infected by any other virus, then this group can be saved.\n\n```\nclass Solution {\n    \n    private static class UnionFind {\n        int[] parent;\n        int[] count;\n        public UnionFind(int N) {\n            this.parent = new int[N];\n            this.count = new int[N];\n            for (int i = 0; i < parent.length; i++) {\n                parent[i] = i;\n                count[i] = 1;\n            }\n        }\n        public void union(int i, int j) {\n            int p1 = find(i);\n            int p2 = find(j);\n            if (p1 != p2) {\n                if (count[p1] >= count[p2]) {\n                    parent[p2] = p1;\n                    count[p1] += count[p2];\n                } else {\n                    parent[p1] = p2;\n                    count[p2] += count[p1];\n                }\n            }\n        }\n        public int find(int i) {\n            while (i != parent[i]) {\n                i = parent[parent[i]];\n            }\n            return i;\n        }\n    }\n    \n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        Arrays.sort(initial);\n        int max = -1;\n        int maxNode = -1;\n        for (int i : initial) {\n            int diff = computeDiff(graph, initial, i);\n            if (diff > max) {\n                max = diff;\n                maxNode = i;\n            }\n        }\n        return maxNode;\n    }\n    \n    private int computeDiff(int[][] graph, int[] initial, int skip) {\n        int N = graph.length;\n        UnionFind uf = new UnionFind(N);\n        for (int i = 0; i < N; i++) {\n            for (int j = 0; j < N; j++) {\n                if (i == skip || j == skip) continue;\n                if (graph[i][j] == 1) {\n                    uf.union(i, j);\n                }\n            }\n        }\n        Map<Integer, Integer> map = new HashMap<>();\n        for (int i : initial) {\n            int p = uf.find(i);\n            map.put(p, map.getOrDefault(p, 0) + 1);\n        }\n        int save = 0;\n        for (int j = 0; j < graph[0].length; j++) {\n            if (graph[skip][j] == 1) {\n                int p = uf.find(j);\n                if (map.getOrDefault(p, 0) == 0) save += uf.count[p];\n            }\n        }\n        return save;\n    }\n}\n```
[]