# 928     Minimize Malware Spread II

## 928. [Minimize Malware Spread II](https://leetcode.com/problems/minimize-malware-spread-ii/)

## 1. Question

(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`

## 2. Implementation

(1) Union Find:

思路: 这题和leetcode 928的区别在于**将这个node从图中删除。**

* 用clean数组，将刚开始未受感染的node标记为1，然后利用union find，将未受感染的node构建并查集
* 查找在initial list里的node属于哪个并查集，用hashmap记录initial list每个node所属的并查集，key是对应cluster的root, value是hashset，保存initial list中被感染的node。
* 对于map中每个cluster的root, 如果root代表的一个集合里只有一个node被感染，则找出拥有node个数最多的这类集合。
* 由于题目要求，如果有多个node都能使被感染的node数量最小时，返回index最小的那个，所以我们需要将initial list排序，并在size相同时，用较小的node更新res

```java
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] clean = new int[n];

        Arrays.fill(clean, 1);

        for (int node : initial) {
            clean[node] = 0;
        }

        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (clean[i] == 1 && clean[j] == 1 && graph[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }

        Arrays.sort(initial);
        Map<Integer, Set<Integer>> map = new HashMap();

        // 对于每个infectedNode, 看看它们属于哪个cluter
        for (int node : initial) {
            for (int i = 0; i < n; i++) {
                if (clean[i] == 1 && graph[node][i] == 1) {
                    int root = uf.find(i);
                    map.putIfAbsent(root, new HashSet());
                    map.get(root).add(node);
                }
            }
        }

        int maxSize = 0, res = initial[0];

        // 对于每个cluster的root，如果它只包含一个infectedNode,则我们可以通过移除ifectedNode
        // 使得整个cluster不被感染
        for (int root : map.keySet()) {
            if (map.get(root).size() == 1) {
                int curSize = uf.getSize(root);
                int infectedNode = map.get(root).iterator().next();

                if (curSize > maxSize) {
                    maxSize = curSize;
                    res = infectedNode;
                }
                else if (curSize == maxSize && infectedNode < res) {
                    res = infectedNode;
                }
            }
        }
        return res;
    }

    class UnionFind {
        int[] parent;
        int[] size;
        int count;

        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            count = n;

            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int node) {
            while (node != parent[node]) {
                node = parent[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int root1 = find(i);
            int root2 = find(j);

            if (root1 == root2) return;

            if (size[root1] < size[root2]) {
                parent[root1] = root2;
                size[root2] += size[root1];
            }
            else {
                parent[root2] = root1;
                size[root1] += size[root2];
            }
            --count;
        }

        public int getSize(int node) {
            return size[node];
        }
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n^2), 主要消耗是在构建union find这一步，空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/union-find/928-minimize-malware-spread-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.