Course4all
Join us on telegram
Home/dsa/Union Find/Minimize Malware Spread

Minimize Malware Spread

Master this topic with zero to advance depth.

Minimize Malware Spread

In a network of nn nodes, some nodes are initially infected with malware. Malware spreads through connected components. You can remove exactly one node from the initial list to minimize total infected nodes. If multiple nodes lead to the same result, return the node with the smallest index.

Optimization Strategy

Only removing an infected node in a component with exactly one initially infected node will actually reduce the total infection (by the size of that component).

Hard

Examples

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

Level II: DFS (Component Analysis)

Intuition

Use DFS to find all connected components in the graph. For each component, count how many nodes in initial are part of it. If only one node is infected, removing it saves all nodes in that component. Track the best node to remove.

⏱ O(N^2).💾 O(N).
java
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length; int[] comp = new int[n]; Arrays.fill(comp, -1); int ids = 0;
        for(int i=0; i<n; i++) if(comp[i]==-1) dfs(graph, i, comp, ids++);
        int[] sz = new int[ids], mal = new int[ids];
        for(int i=0; i<n; i++) sz[comp[i]]++;
        for(int i : initial) mal[comp[i]]++;
        Arrays.sort(initial); int res = initial[0], maxS = -1;
        for(int i : initial) {
            if(mal[comp[i]]==1 && sz[comp[i]] > maxS) { maxS = sz[comp[i]]; res = i; }
        }
        return res;
    }
    void dfs(int[][] g, int u, int[] comp, int id) {
        comp[u] = id; for(int v=0; v<g.length; v++) if(g[u][v]==1 && comp[v]==-1) dfs(g, v, comp, id);
    }
}
Approach 2

Level III: Union-Find (Component Size Analysis)

Intuition

Build components using Union-Find and record the size of each. For each component, count how many nodes from initial are in it. If a component has exactly one initial node, moving that node saves size nodes. Pick the one that saves the most.

⏱ O(N^2) to build graph components.💾 O(N).
java
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] p = new int[n]; for(int i=0; i<n; i++) p[i]=i;
        int[] sz = new int[n]; Arrays.fill(sz, 1);
        for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) if(graph[i][j]==1) union(p, sz, i, j);
        int[] count = new int[n];
        for(int i : initial) count[find(p, i)]++;
        Arrays.sort(initial);
        int res = initial[0], maxSave = -1;
        for(int i : initial) {
            int root = find(p, i);
            if(count[root] == 1) {
                if(sz[root] > maxSave) { maxSave = sz[root]; res = i; }
            }
        }
        return res;
    }
    int find(int[] p, int i) { return p[i]==i ? i : (p[i]=find(p, p[i])); }
    void union(int[] p, int[] sz, int i, int j) {
        int r1=find(p,i), r2=find(p,j);
        if(r1 != r2) { p[r1]=r2; sz[r2]+=sz[r1]; }
    }
}
← Previous QuestionRegions Cut By Slashes
Next Question →Making a Large Island