Java (42ms) using Union Find Set and Brute Force with explaination
Idea is that, first, we disable all the nodes from initial list. And build the union find set.\n\nThen we try removing each node from the initial list in way of
Idea is that, first, we disable all the nodes from initial list. And build the union find set.\n\nThen we try removing each node from the initial list in way of brute-force . \nSay in this trial, we will remove initial[i]. We execute the trial by marking all the components linked by the elements from the init list except initial[i]. Then we sum up the number of all the linked components at the end of the trial, we compare the sum to a global_min. Hence we may find a node that results in a minimum M(initial)\n\nNote in my implementation of UFS, I use a parent array. In my array, if a node is not root, then its value is its parent index, else if this is a root, its value equals negative (number of this component). Hence we may mark the root node and the parent relationship using only one value.\n\n(Check this out if you don\'t know UFS: https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86)\n```\nclass Solution {\n    int[] parent;\n    \n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        int N = graph.length;\n        parent = new int[N];\n        Arrays.fill(parent, -1);\n        Arrays.sort(initial);   // sort the initial list to get the min index of result in case of a tie\n        Set<Integer> set = new HashSet<>();\n        for (int n : initial) set.add(n);\n        \n        // build the union find set disabling the init elements\n        for (int i = 0; i < N; i++) {\n            if (set.contains(i)) continue;\n            for (int j = 0; j < N; j++) {\n                if (set.contains(j)) continue;\n                if (graph[i][j] == 1) {\n                    union(i, j);\n                }\n            }\n        }\n        \n        int total = Integer.MAX_VALUE;\n        int res = -1;\n        for (int skip = 0; skip < initial.length; skip++) {\n            Map<Integer, Integer> cnts = new HashMap<>();\n            for (int mal = 0; mal < initial.length; mal++) {\n                if (mal == skip) continue;\n                \n                int malId = initial[mal];\n                for (int i = 0; i < N; i++) {\n                    if (i == initial[skip]) continue;\n                    \n                    if (graph[malId][i] == 1) {\n                        int root = find(i);\n                        cnts.putIfAbsent(root, -parent[root]);\n                    }\n                    \n                }\n                \n            }\n            \n            int sum = 0;\n            for (int v : cnts.values()) {\n                sum += v;\n            }\n            \n            // if removing initial[skip] causes less spread\n            if (sum < total) {\n                total = sum;\n                res = initial[skip];\n                \n            }\n        }\n        \n        return res;\n    }\n    \n    private int find(int x) {\n        if (parent[x] < 0) return x;\n        parent[x] = find(parent[x]);\n        return parent[x];\n    }\n    \n    private void union(int x, int y) {\n        x = find(x);\n        y = find(y);\n        if (x == y) return;\n        if (parent[x] <= parent[y]) {\n            parent[x] += parent[y];\n            parent[y] = x;\n        } else {\n            parent[y] += parent[x];\n            parent[x] = y;\n        }\n    }\n}\n```
[]