class Solution:
def minMalwareSpread(self, graph, initial):
n = len(graph)
initial_set = set(initial)
# Find connected components using Union Find
parent = [i for i in range(n)]
def find(u):
while parent[u] != u:
parent[u] = parent[parent[u]]
u = parent[u]
return u
def union(u, v):
pu, pv = find(u), find(v)
if pu != pv:
parent[pu] = pv
# Build union-find structure
for i in range(n):
for j in range(i+1, n):
if graph[i][j]:
union(i, j)
# Count size and malware in each component
size = [0]*n
malware = [0]*n
for i in range(n):
root = find(i)
size[root] += 1
for node in initial:
root = find(node)
malware[root] += 1
# Try removing each initial node
result = None
max_saved = -1
for node in sorted(initial):
root = find(node)
if malware[root] == 1:
saved = size[root]
if saved > max_saved or (saved == max_saved and node < result):
max_saved = saved
result = node
if result is None:
result = min(initial)
return result
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
vector<int> parent(n);
for (int i = 0; i < n; ++i) parent[i] = i;
function<int(int)> find = [&](int u) {
if (parent[u] != u) parent[u] = find(parent[u]);
return parent[u];
};
auto unite = [&](int u, int v) {
int pu = find(u), pv = find(v);
if (pu != pv) parent[pu] = pv;
};
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (graph[i][j]) unite(i, j);
vector<int> size(n, 0), malware(n, 0);
for (int i = 0; i < n; ++i) size[find(i)]++;
for (int node : initial) malware[find(node)]++;
int result = -1, max_saved = -1;
sort(initial.begin(), initial.end());
for (int node : initial) {
int root = find(node);
if (malware[root] == 1) {
if (size[root] > max_saved) {
max_saved = size[root];
result = node;
}
}
}
if (result == -1)
result = *min_element(initial.begin(), initial.end());
return result;
}
};
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
int[] parent = new int[n];
for (int i = 0; i < n; ++i) parent[i] = i;
// Union Find
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (graph[i][j] == 1) union(parent, i, j);
int[] size = new int[n];
int[] malware = new int[n];
for (int i = 0; i < n; ++i) size[find(parent, i)]++;
for (int node : initial) malware[find(parent, node)]++;
int result = -1, maxSaved = -1;
Arrays.sort(initial);
for (int node : initial) {
int root = find(parent, node);
if (malware[root] == 1) {
if (size[root] > maxSaved) {
maxSaved = size[root];
result = node;
}
}
}
if (result == -1)
result = initial[0];
return result;
}
private int find(int[] parent, int u) {
if (parent[u] != u) parent[u] = find(parent, parent[u]);
return parent[u];
}
private void union(int[] parent, int u, int v) {
int pu = find(parent, u), pv = find(parent, v);
if (pu != pv) parent[pu] = pv;
}
}
var minMalwareSpread = function(graph, initial) {
const n = graph.length;
const parent = Array.from({length: n}, (_, i) => i);
function find(u) {
while (parent[u] !== u) {
parent[u] = parent[parent[u]];
u = parent[u];
}
return u;
}
function union(u, v) {
const pu = find(u), pv = find(v);
if (pu !== pv) parent[pu] = pv;
}
for (let i = 0; i < n; ++i)
for (let j = i + 1; j < n; ++j)
if (graph[i][j]) union(i, j);
const size = Array(n).fill(0), malware = Array(n).fill(0);
for (let i = 0; i < n; ++i) size[find(i)]++;
for (const node of initial) malware[find(node)]++;
let result = null, maxSaved = -1;
initial.sort((a, b) => a - b);
for (const node of initial) {
const root = find(node);
if (malware[root] === 1) {
if (size[root] > maxSaved) {
maxSaved = size[root];
result = node;
}
}
}
if (result === null)
result = Math.min(...initial);
return result;
};
Given a network of n computers represented by an n x n adjacency matrix graph, some computers are initially infected with malware, listed in the array initial. Malware spreads to directly connected computers unless one infected node is removed from the network before the spread begins. Your task is to choose exactly one node from initial to remove, so that the final number of infected nodes is minimized. If there are multiple choices, return the node with the smallest index.
graph[i][i] = 1).initial.At first glance, it may seem like we should try removing each infected node and simulate the malware spread for each case. However, this brute-force approach is inefficient for large networks. To optimize, we need to understand how malware propagates: it spreads within connected components of the graph. If a component contains more than one initially infected node, removing any single node won’t stop the rest from infecting the component. But if a component has exactly one infected node, removing it will save the entire component from infection. This realization suggests we should focus on the structure of connected components and the distribution of infected nodes within them.
initial, if its component contains only that single infected node, removing it will prevent the entire component from being infected. The number of nodes saved equals the component’s size.initial.We use Union-Find for efficiency, as it allows us to quickly determine which component a node belongs to and to merge groups as we process the adjacency matrix.
Input:
graph = [[1,1,0],[1,1,0],[0,0,1]]
initial = [0,1]
initial, which is 0.
Another example:
graph = [[1,0,0],[0,1,0],[0,0,1]]
initial = [0,2]
initial, simulate the infection spread, which is O(n^2) per simulation, leading to O(n^3) overall.initial). Thus, overall complexity is O(n^2).The problem leverages the insight that malware spreads only within connected components, and that components with a single initial infection can be completely saved by removing that node. Using Union-Find makes it efficient to identify and analyze these components. The solution is both elegant and efficient, reducing what could be a cubic brute-force problem to a quadratic one by focusing on the graph’s structure and the distribution of infections.