Minimize Malware Spread

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

Note that if a node was removed from the initial 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

分析

Union find

注意要求每个Group大小，只要加个size数组就好，初始为一，在Union更新一下就好

求出每个组大小，再求每个组里有几个initial的malware。只对含一个malware的组进行计算。（多于一个的话抽几个都一样）

class Solution {
    int[] f;
    int[] size;
    
    public int minMalwareSpread(int[][] graph, int[] initial) {
        if(graph == null || graph.length== 0){
            return 0;
        }
        int n =graph.length;
    
        f = new int[n];
        size = new int[n];
        //忘了初始化，错半死
        for (int i = 0; i < n; i++) {
            f[i] = i;
            size[i] = 1;
        }
        for(int i = 0; i < n; i ++){
            for(int j = i+1; j < n; j++){
                if(graph[i][j] == 1){
                    union(i,j);
                }
            }
        }
        
        Arrays.sort(initial);
        int[] malware =new int[n];
        for (int i : initial){
            malware[find(i)] ++;
        }
        int res= 0, x = initial[0];
        for(int i : initial){
            int ri = find(i);
            if(malware[ri] == 1){
                if (res < size[ri]){
                    res = size[ri];
                    x = i;
                }
                
            }
        }
        return x;
    }
    
    public int find(int x){
        if(f[x] == x){
            return x;
        }
        return f[x] = find(f[x]);
    }
    
    public void union(int x, int y){
        int rx = find(x);
        int ry = find(y);
        if(rx != ry){
            f[rx] = ry;
            size[ry] += size[rx];
        }
        
    }
    
    
}

dfs

比较Unionfind,dfs能得到一个Group内具体的点。dfs得到group里点的set。然后和initial做集合&，有交集且为1（就是当前node）。则比较历史数值，取更好的。

这里注意map的用法map[max(map)]. 这里max（map）得到的是最大key

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        if not graph or not graph[0]:
            return 0
        d = [-1,0,1,0,-1]  
        n = len(graph)
        ts = set()
        def dfs(i,s):
            s.add(i)
            for j in range(n):
                if j not in s and graph[i][j] == 1:
                    dfs(j,s)
            
        initial = set(initial)
        rank = collections.defaultdict(list)
        save,res = 0,min(initial)
        for i in initial:
            if i not in ts:
                s= set()
                dfs(i,s)
                if s&initial == {i}:
                    if save < len(s) or save == len(s) and res > i:
                        res = i
                        save = len(s)
                ts |= s
            
        return res
                    
            
            
        
        
        

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        if not graph or not graph[0]:
            return 0
        d = [-1,0,1,0,-1]  
        n = len(graph)
        ts = set()
        def dfs(i,s):
            s.add(i)
            for j in range(n):
                if j not in s and graph[i][j] == 1:
                    dfs(j,s)
            
        initial = set(initial)
        rank = collections.defaultdict(list)
        save,res = 0,min(initial)
        for i in initial:
            if i not in ts:
                s= set()
                dfs(i,s)
                if s&initial == {i}:
                    if save < len(s) or save == len(s) and res > i:
                        res = i
                        save = len(s)
                ts |= s
            
        return res