Minimize Malware Spread

Problem Statement

In the given problem, we have a network represented by an adjacency matrix named graph, where each node is identified by indices and its connections to other nodes by '1's (being connected) and '0's (not connected). Some nodes, listed in initial, start infected by malware. Malware spreads between directly connected nodes; if one node is infected, the directly connected node gets infected as well.

The challenge involves deciding which one node, when removed from the initial set of infected nodes, will result in the minimum possible number of eventually infected nodes (M(initial)), after the spread of malware stabilizes (i.e., no further infections are possible). If removing multiple nodes yields the same minimized M(initial), the node with the smallest index among them is to be returned. Even if a node is removed from the initial set, it's possible it might still end up infected if connected to other infected nodes.

Examples

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

Constraints

• n == graph.length
• n == graph[i].length
• 2 <= n <= 300
• graph[i][j] is 0 or 1.
• graph[i][j] == graph[j][i]
• graph[i][i] == 1
• 1 <= initial.length <= n
• 0 <= initial[i] <= n - 1
• All the integers in initial are unique.

Approach and Intuition

The given problem involves understanding the dynamics of network spread and identifying critical nodes whose removal minimally impacts the network's health relative to malware spread. Below outlines the steps and intuition behind the problem-solving approach:

1. Understand the Network from the Adjacency Matrix:

   • The graph[i][j] == 1 reflects that there is a direct connection between the i-th and j-th nodes. Similarly, graph[i][j] == 0 means no direct connection.
   • The matrix is symmetric (i.e., graph[i][j] == graph[j][i]), which indicates that connections are bidirectional.

2. Consider the Malware Spread:

   • Initiate by marking the nodes given in the initial array as infected. This set changes dynamically as the malware spreads.
   • Malware spreads to any connected node if one of the nodes is infected, particularly noted by the connections denoted by '1' in the adjacency matrix.

3. Simulate the Impact of Removing Each "Initial" Node:

   • For each node in initial, simulate the scenario where the node is not initially infected and propagate the spread to compute the final number of infected nodes, M', without this node.
   • Note, the removed node might still get infected if later connected to another infected node through its edges.

4. Calculate and Compare for Minimum Spread:

   • Track which removed node results in the smallest number of infected nodes.
   • In conditions where multiple nodes lead to the same minimized M', choose the node with the smallest index.

5. Implementation Approach:

   • Depth-first search (DFS) or breadth-first search (BFS) can be used to propagate the infection and estimate the final count of infected nodes for any configuration of initially infected nodes.
   • Optimize with marking visited nodes and skipping over already processed configurations.

This problem integrates elements of graph traversal, infection dynamics spread modeling, and optimization by choosing nodes whose removal best mitigates a negative consequence (infection spread). Understanding the structure and connections in graph is crucial for efficiently simulating and deciding the strategic node removal.

Solutions

class Solution {
    public int findMinMalwareSpread(int[][] graph, int[] infected) {
        int size = graph.length;
        UnionFind uf = new UnionFind(size);
        for (int i = 0; i < size; ++i)
            for (int j = i + 1; j < size; ++j)
                if (graph[i][j] == 1)
                    uf.union(i, j);

        int[] infectedCount = new int[size];
        for (int v : infected)
            infectedCount[uf.find(v)]++;

        int minHeight = -1, minIndex = -1;
        for (int v : infected) {
            int root = uf.find(v);
            if (infectedCount[root] == 1) { // single infection
                int clusterSize = uf.clusterSize(root);
                if (clusterSize > minHeight) {
                    minHeight = clusterSize;
                    minIndex = v;
                } else if (clusterSize == minHeight && v < minIndex) {
                    minHeight = clusterSize;
                    minIndex = v;
                }
            }
        }

        if (minIndex == -1) {
            minIndex = Integer.MAX_VALUE;
            for (int v : infected)
                minIndex = Math.min(minIndex, v);
        }
        return minIndex;
    }
}

class UnionFind {
    int[] parent, size;

    UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;

        size = new int[n];
        Arrays.fill(size, 1);
    }

    public int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootA] = rootB;
            size[rootB] += size[rootA];
        }
    }

    public int clusterSize(int x) {
        return size[find(x)];
    }
}