924 Minimize Malware Spread

924. Minimize Malware Spread

1. Question

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

Some nodesinitialare 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.

SupposeM(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. Return the node that if removed, would minimize M(initial). If multiple nodes could be removed to minimizeM(initial), return such a node with the smallest index.

Note that if a node was removed from theinitial list of infected nodes, it may still be infected later as a result of the malware spread.

Example 1:

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

Example 2:

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

Example 3:

Input: 
graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
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:

思路: 这题要求我们在输入的initial list里移除一个node，使得最后感染的node的数量最少。注意这里移除的意思是指，让initial list中原本被感染的node变成不被感染，而不是说将这个node从图中删除, 这点是和leetcode 928的区别。

• 利用union find，构建并查集

• 查找在initial list里的node属于哪个并查集，用hashmap记录initial list每个node所属的并查集，以及其所对应的个数。如果一个并查集里含有两个或以上的node被感染，则根据题意只能让一个node不感染，那这个并查集不管移除哪个node都不能避免集合里的node不被感染。如果一个集合里只有一个node被感染，则找出拥有node个数最多的这类集合。

• 由于题目要求，如果有多个node都能使被感染的node数量最小时，返回index最小的那个，所以我们需要将initial list排序

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

        UnionFind uf = new UnionFind(n);

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

        Map<Integer, Integer> map = new HashMap();

        for (int node : initial) {
            int root = uf.find(node);
            map.put(root, map.getOrDefault(root, 0) + 1);
        }

        Arrays.sort(initial);

        int res = 0, maxSize = -1;

        for (int node : initial) {
            int root = uf.find(node);
            // 如果map.get(root) > 1, 无论如何都无法使得root所在的集合里node不被感染
            int infectedNodes = map.get(root) == 1 ? uf.getSize(root) : 0;

            if (infectedNodes  > maxSize) {
                maxSize = infectedNodes;
                res = node;
            }
        }
        return res;
    }

    class UnionFind {
        int[] root;
        int[] size;

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

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

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

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);

            if (rootI == rootJ) return;

            if (size[rootI] < size[rootJ]) {
                root[rootI] = rootJ;
                size[rootJ] += size[rootI];
            }
            else {
                root[rootJ] = root[rootJ];
                size[rootI] += size[rootJ];
            }
        }

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

3. Time & Space Complexity

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