Minimize Malware Spread II

• Sort the initial array in ascending order. This helps in tie-breaking, as we will find the smallest index first.
• Initialize minInfectedCount to a value larger than any possible outcome (e.g., n + 1) and resultNode to the first element of the sorted initial array.
• Iterate through each nodeToRemove in the sorted initial array.
• For each nodeToRemove, simulate the spread:
  • Create a set infected and a queue for BFS.
  • Add all nodes from initial (except nodeToRemove) to both the infected set and the queue.
  • Perform a BFS. In each step, for a node u, explore its neighbors v. If v is connected, not the nodeToRemove, and not already infected, add it to the infected set and the queue.
• After the BFS completes, the size of the infected set is the total number of infected nodes for this scenario.
• If this count is less than minInfectedCount, update minInfectedCount with the new count and resultNode to nodeToRemove.
• After checking all nodes in initial, return resultNode.

The core idea is to try removing each node from the initial set one by one. For each node u in initial that we consider removing, we define a new set of infected sources, which is initial excluding u. We also treat u as a removed node from the graph, meaning it cannot be visited or spread malware. We then perform a graph traversal (like Breadth-First Search or Depth-First Search) starting from all the new sources. We count the total number of nodes visited during this traversal. This gives us the final number of infected nodes, M, for the scenario where u is removed. We keep track of the node u that leads to the minimum M found so far. To handle ties (multiple nodes giving the same minimum M), we should return the one with the smallest index. A simple way to do this is to sort the initial array first and then iterate. The first node that yields the minimum M will be the answer.

1import java.util.*;2 3class Solution {4    public int minMalwareSpread(int[][] graph, int[] initial) {5        Arrays.sort(initial);6        int n = graph.length;7        int minInfected = n + 1;8        int resultNode = -1;9 10        for (int nodeToRemove : initial) {11            Set<Integer> infected = new HashSet<>();12            Queue<Integer> queue = new LinkedList<>();13            14            for (int startNode : initial) {15                if (startNode != nodeToRemove) {16                    infected.add(startNode);17                    queue.add(startNode);18                }19            }20 21            // Using a temporary set to avoid ConcurrentModificationException22            Set<Integer> currentInfected = new HashSet<>(infected);23            while (!queue.isEmpty()) {24                int u = queue.poll();25                for (int v = 0; v < n; v++) {26                    if (graph[u][v] == 1 && v != nodeToRemove && !currentInfected.contains(v)) {27                        currentInfected.add(v);28                        queue.add(v);29                    }30                }31            }32 33            if (currentInfected.size() < minInfected) {34                minInfected = currentInfected.size();35                resultNode = nodeToRemove;36            }37        }38        return resultNode;39    }40}

• Put all nodes from initial into a HashSet for efficient lookups.
• Find connected components of the graph formed by non-initial nodes. Use DFS/BFS.
  • Maintain a componentId array to map each node to its component ID.
  • Maintain a componentSize array to store the size of each component.
• Create a map componentToInfectors to store the set of initial nodes that are adjacent to each healthy component.
• Iterate through each initial node u. For each neighbor v of u that is not an initial node, find its component ID and add u to the set of infectors for that component.
• Initialize a savedCount array of size n to zeros.
• Iterate through the componentToInfectors map. If a component is infected by exactly one initial node u, add the size of this component to savedCount[u].
• Sort the initial array to handle tie-breaking.
• Find the node u in initial that has the maximum value in savedCount[u]. This is the node to remove. Return this node.

The key insight is that the final number of infected nodes depends on which "healthy" components get infected. A healthy component is a connected group of nodes that are not in the initial set. The strategy is as follows:

1. Isolate Healthy Components: First, we identify the connected components in the graph consisting only of non-initial nodes. We can use DFS or BFS to do this. For each such component, we calculate its size and assign a unique ID.
2. Map Infectors to Components: Next, for each healthy component, we identify which nodes from the initial set are connected to it. We can build a map where keys are component IDs and values are sets of initial nodes that can infect them.
3. Calculate Saved Nodes: A component will be saved from infection if and only if we remove its only source of infection. So, we look for components that are connected to exactly one initial node. For each such component, if we remove its single infector, we "save" all nodes in that component. We can maintain an array, say savedCount, where savedCount[u] stores the total number of nodes that would be saved by removing initial node u.
4. Find the Best Node: Finally, we iterate through the initial nodes. The node u that has the maximum savedCount[u] is the one that minimizes the final infection count. If there's a tie, we choose the one with the smallest index. This approach is more efficient because it processes the graph structure once to find components and then uses this information to quickly evaluate the outcome of removing each initial node.

1import java.util.*;2 3class Solution {4    public int minMalwareSpread(int[][] graph, int[] initial) {5        int n = graph.length;6        Set<Integer> initialSet = new HashSet<>();7        for (int node : initial) {8            initialSet.add(node);9        }10 11        // 1. Find components of the graph without initial nodes12        int[] componentId = new int[n];13        Arrays.fill(componentId, -1);14        int[] componentSize = new int[n];15        int cId = 0;16        for (int i = 0; i < n; i++) {17            if (!initialSet.contains(i) && componentId[i] == -1) {18                int size = 0;19                Queue<Integer> q = new LinkedList<>();20                q.add(i);21                componentId[i] = cId;22                size++;23                while (!q.isEmpty()) {24                    int u = q.poll();25                    for (int v = 0; v < n; v++) {26                        if (graph[u][v] == 1 && !initialSet.contains(v) && componentId[v] == -1) {27                            componentId[v] = cId;28                            size++;29                            q.add(v);30                        }31                    }32                }33                componentSize[cId] = size;34                cId++;35            }36        }37 38        // 2. Map components to their initial node infectors39        Map<Integer, Set<Integer>> componentToInfectors = new HashMap<>();40        for (int u : initial) {41            Set<Integer> infectedComponents = new HashSet<>();42            for (int v = 0; v < n; v++) {43                if (graph[u][v] == 1 && !initialSet.contains(v)) {44                    infectedComponents.add(componentId[v]);45                }46            }47            for (int infectedCId : infectedComponents) {48                componentToInfectors.computeIfAbsent(infectedCId, k -> new HashSet<>()).add(u);49            }50        }51 52        // 3. Calculate how many nodes are saved by removing each initial node53        int[] savedCount = new int[n];54        for (Map.Entry<Integer, Set<Integer>> entry : componentToInfectors.entrySet()) {55            if (entry.getValue().size() == 1) {56                int infector = entry.getValue().iterator().next();57                int cSize = componentSize[entry.getKey()];58                savedCount[infector] += cSize;59            }60        }61 62        // 4. Find the best node to remove63        Arrays.sort(initial);64        int maxSaved = -1;65        int resultNode = initial[0];66        for (int u : initial) {67            if (savedCount[u] > maxSaved) {68                maxSaved = savedCount[u];69                resultNode = u;70            }71        }72        return resultNode;73    }74}