[LeetCode] 928. Minimize Malware Spread II

[grandyang]

(This problem is the same as  Minimize Malware Spread , with the differences bolded.)

In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.

Some nodes initial are initially infected by malware.  Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware.  This spread of malware will continue until no more nodes can be infected in this manner.

Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.

We will remove one node from the initial list,  completely removing it and any connections from this node to any other node.  Return the node that if removed, would minimize M(initial).  If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.

Example 1:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

Example 2:

Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1

Example 3:

Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1

Note:

1. 1 < graph.length = graph[0].length <= 300
2. 0 <= graph[i][j] == graph[j][i] <= 1
3. graph[i][i] = 1
4. 1 <= initial.length < graph.length
5. 0 <= initial[i] < graph.length

这道题是之前那道 Minimize Malware Spread 的拓展，实际上只是修改了一个地方，就是文中加粗的地方，说的是每次直接将这个结点去掉，而不是像之前的题目那样只是将其不当做感染源。那么二者到底有什么区别呢，实际上并不是在所有的 test case 上都有区别，只是部分会有。比如对于 graph=[[1,1,0],[1,1,1],[0,1,1]], initial=[0,1] 来说，可以发现结点的链接情况是 0-1-2，感染源结点是0和1，若是按之前题目的要求，移除0和1都不会减少最终感染个数，但是应该返回结点0，因为其 index 小。但是应用此题的条件，就一定要返回结点1，因为移除结点1之后，就断开了结点0和结点2的连接，最终只有病毒源结点0会保持感染状态，这就是二者的区别所在。解题思路完全可以在之前那道题 Minimize Malware Spread 的基础上进行修改，最简单暴力的修改其实是新建一个 graph 的副本，然后当要删掉某个结点i的时候，将所有的 graph[i][:] 和 graph[:][i] 都赋值为0即可，这样修改邻接矩阵就相当于断开了结点i和其他所有结点之间的连接，博主亲测解法1和解法2都可以用此方法通过。当然也可以用其他的方法，这里博主将要删除的结点 num 带入到了子函数中，在 BFS 中遍历某个结点的所有邻接点的时候，只要多加个判断，跳过 num 结点也是可以的，参见代码如下：

解法一：

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int mn = INT_MAX, res = 0;
        unordered_set<int> infected(initial.begin(), initial.end());
        for (int num : initial) {
            infected.erase(num);
            int cnt = helper(graph, infected, num);
            if (cnt < mn || (cnt == mn && num < res)) {
                mn = cnt;
                res = num;
            }
            infected.insert(num);
        }
        return res;
    }
    int helper(vector<vector<int>>& graph, unordered_set<int> infected, int num) {
        queue<int> q;
        for (int num : infected) q.push(num);
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            for (int i = 0; i < graph[t].size(); ++i) {
                if (i == num || graph[t][i] != 1 || infected.count(i)) continue;
                infected.insert(i);
                q.push(i);
            }
        }
        return infected.size();
    }
};

当然对于 DFS 的解法也可以做类似的处理，除了上面提到的建立 graph 副本并修改的方法之外，也可以用其他的方法。这里博主对于每个要移除的结点 num，先将其加入 visited 之中，然后在遍历的时候，只对非 num 结点调用递归函数，可以得到同样的结果，参见代码如下：

解法二：

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int mn = INT_MAX, res = 0;
        unordered_set<int> infected(initial.begin(), initial.end());
        for (int num : initial) {
            infected.erase(num);
            int cnt = 0;
            unordered_set<int> visited{{num}};
            for (int cur : infected) {
                if (cur != num) helper(graph, cur, visited, cnt);
            }
            if (cnt < mn || (cnt == mn && num < res)) {
                mn = cnt;
                res = num;
            }
            infected.insert(num);
        }
        return res;
    }
    void helper(vector<vector<int>>& graph, int cur, unordered_set<int>& visited, int& cnt) {
        if (visited.count(cur)) return;
        visited.insert(cur);
        ++cnt;
        for (int i = 0; i < graph[cur].size(); ++i) {
            if (graph[cur][i] != 1) continue;
            helper(graph, i, visited, cnt);
        }
    }
};

讨论：博主本想将之前那道 Minimize Malware Spread 的解法三也修改一下用到这里，但发现比较难修改，论坛虽然也有一些使用联合查找 Union Find 来做的解法，但是感觉都比较复杂，这里就不写了，若哪位看官大神可以将之前的解法三移植过来，请务必留言告诉博主哈～

Github 同步地址:

#928

类似题目：

Minimize Malware Spread

参考资料：

https://leetcode.com/problems/minimize-malware-spread-ii/

https://leetcode.com/problems/minimize-malware-spread-ii/discuss/217529/c%2B%2B-solution-bfs

https://leetcode.com/problems/minimize-malware-spread-ii/discuss/184645/Straightforward-DFS-Java-6-ms

LeetCode All in One 题目讲解汇总(持续更新中...)