Sponsored
Sponsored
One way to solve the problem is by using the Union-Find algorithm (also known as Disjoint Set Union or DSU) to identify connected components of the graph. Each component can either have one or more initially infected nodes. The objective is to remove a node such that the size of the initially infected nodes is minimized after malware spreads. This approach groups nodes together and calculates the effect of each removal by considering the infection spread of each distinct component.
Time Complexity: O(n2) due to graph iteration, where n is the number of nodes. The union-find operations are nearly O(1) on average.
Space Complexity: O(n) for the union-find data structures.
1class UnionFind {
2 constructor(size) {
3 this.parent = Array.from({ length: size }, (_, i) => i);
4 this.rank = Array(size).fill(0);
5 }
6
7 find(node) {
8 if (this.parent[node] !== node) {
9 this.parent[node] = this.find(this.parent[node]);
10 }
11 return this.parent[node];
12 }
13
14 union(node1, node2) {
15 const root1 = this.find(node1);
16 const root2 = this.find(node2);
17 if (root1 !== root2) {
18 if (this.rank[root1] > this.rank[root2]) {
19 this.parent[root2] = root1;
20 } else if (this.rank[root1] < this.rank[root2]) {
21 this.parent[root1] = root2;
22 } else {
23 this.parent[root2] = root1;
24 this.rank[root1]++;
25 }
26 }
27 }
28}
29
30function minMalwareSpread(graph, initial) {
31 const n = graph.length;
32 const uf = new UnionFind(n);
33
34 for (let i = 0; i < n; i++) {
35 for (let j = 0; j < n; j++) {
36 if (graph[i][j] === 1) {
37 uf.union(i, j);
38 }
39 }
40 }
41
42 initial.sort((a, b) => a - b);
43
44 const infectedCount = Array(n).fill(0);
45 initial.forEach(node => {
46 infectedCount[uf.find(node)]++;
47 });
48
49 let maxSaved = -1;
50 let bestNode = initial[0];
51
52 initial.forEach(node => {
53 const root = uf.find(node);
54 if (infectedCount[root] === 1) {
55 const saved = graph.reduce((acc, _, i) => acc + (uf.find(i) === root ? 1 : 0), 0);
56 if (saved > maxSaved) {
57 maxSaved = saved;
58 bestNode = node;
59 }
60 }
61 });
62
63 return bestNode;
64}This JavaScript solution leverages a union-find structure to group graph nodes. The function strategically chooses node removal to minimize infection, implementing infection counting and savings calculations within the graph's components.
This approach uses Depth-First Search (DFS) or Breadth-First Search (BFS) to analyze the graph, identify connected components, and determine component-wise infections. The solution calculates how many vertices are infected by each initial node within its component and selects a node for removal that would minimize the spread as much as possible.
Time Complexity: O(n2) given graph traversal and sorting; Space Complexity: O(n) for BFS structures and tracking components.
1#include <stdio.h>
2
The C implementation applies DFS to mark nodes into components, computes the infected and component sizes, determines a node to knock off minimizing max infected. Sorting the nodes ensures minimal index prioritization.