Straightforward DFS Java  6 ms
Just count how many nodes can be saved by removing each of the candidates. O(N^2)\n\nOnly one place needs attention is once we encounter a malware neighbor duri
Just count how many nodes can be saved by removing each of the candidates. O(N^2)\n\nOnly one place needs attention is once we encounter a malware neighbor during search, we will add current node to malware set as well. \n\nWhy? Because in order to make any node from "will be infected" to "won\'t be infected" by removing one of the initial malwared nodes, one necessary property for such a node is that **it cannot be conencted to more than 1 initial malwared nodes** **(notice "connected" means there is a path between two nodes)** as in that case removing 1 node doesn\'t help, it will still be infected from other direction (also obviously it has to be connected to at least 1 initial malware node, which made it has to be connected to exactly 1 initial malwared node). \n\nGiven that, we can conclude that in every search branch in our DFS tree, if we encounter any malware neighbor along the search, it means the node we are at right now (actually we can even say the whole branch starting from the root) is not qualified as a "count" since it is connected to more than 1 initial malwared node (as the root of DFS is always a malware node since we start DFS from each initial malware node). So by knowing that we can simply add node like this to malware set which can avoid repeated visit and speed up!\n\n                             \n\n\n\n\n![image](https://assets.leetcode.com/users/xxj79/image_1546028094.png)\n\n\n      \n\t     \n\t\t \nIn the above picture, A & D are initailly infected. B & C are both considered "unqualified" here as either by removing A or D doesn\'t change B\'s or C\'s final state as they will be infected from other direction anyways.\n\n\n   \n   \n     \n\t \n```\nclass Solution {\n    public int minMalwareSpread(int[][] graph, int[] initial) {\n        Arrays.sort(initial);\n        \n        Set<Integer> mal = new HashSet<>();\n        for(int n : initial) {\n            mal.add(n);\n\t\t}\n        \n        int max = -1, ret = -1;\n        for(int n : initial){\n            int save = 0;\n            Set<Integer> visited = new HashSet<>();\n            visited.add(n);\n            for(int i = 0; i<graph.length; i++){\n                if(i != n && graph[n][i] == 1){\n                    int temp = dfs(i, visited, mal, graph);\n                    if(temp < 0) continue; // encountered malware during exploration, meaning this whole branch doesn\'t count/contribute\n                    save += temp;\n                }\n            }\n            if(save > max){ \n                ret = n;\n                max = save;\n            }\n        }\n        return ret;\n    }\n    \n    private int dfs(int n, Set<Integer> visited, Set<Integer> mal, int[][] graph){\n        if(visited.contains(n)) return 0;\n        if(mal.contains(n)) return -1;\n        visited.add(n);\n        \n        int ret = 1; // current node saved (at least for now)\n        for(int i = 0; i<graph.length; i++){\n            if(i != n && graph[n][i] == 1){\n                int temp = dfs(i, visited, mal, graph);\n                if(temp == -1) {\n                    mal.add(n); // has neighbor malware, marked as malware as well\n                    return -1; // return -1, indicating there\'s malware downstream in this branch, whole branch unqualified!\n                }\n                ret += temp;\n            }\n        }\n        return ret;\n    }\n}\n```
[]