928 Minimize Malware Spread II

928. Minimize Malware Spread II

1. Question

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

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, 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 minimizeM(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

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)