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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int find(int parent[], int i) {
6 if (parent[i] != i)
7 parent[i] = find(parent, parent[i]);
8 return parent[i];
9}
10
11void unionSets(int parent[], int rank[], int x, int y) {
12 int rootX = find(parent, x);
13 int rootY = find(parent, y);
14 if (rootX != rootY) {
15 if (rank[rootX] > rank[rootY])
16 parent[rootY] = rootX;
17 else if (rank[rootX] < rank[rootY])
18 parent[rootX] = rootY;
19 else {
20 parent[rootY] = rootX;
21 rank[rootX]++;
22 }
23 }
24}
25
26int minMalwareSpread(int** graph, int graphSize, int* initial, int initialSize) {
27 int* parent = (int*)malloc(graphSize * sizeof(int));
28 int* rank = (int*)malloc(graphSize * sizeof(int));
29 for (int i = 0; i < graphSize; i++) {
30 parent[i] = i;
31 rank[i] = 0;
32 }
33
34 for (int i = 0; i < graphSize; i++) {
35 for (int j = 0; j < graphSize; j++) {
36 if (graph[i][j] == 1) {
37 unionSets(parent, rank, i, j);
38 }
39 }
40 }
41
42 // Initialize infected count
43 int* infectedCount = (int*)malloc(graphSize * sizeof(int));
44 memset(infectedCount, 0, graphSize * sizeof(int));
45
46 // Count infections
47 for (int i = 0; i < initialSize; i++) {
48 int root = find(parent, initial[i]);
49 infectedCount[root]++;
50 }
51
52 // Sort initial
53 int tmp;
54 for (int i = 0; i < initialSize; i++) {
55 for (int j = i + 1; j < initialSize; j++) {
56 if (initial[i] > initial[j]) {
57 tmp = initial[i];
58 initial[i] = initial[j];
59 initial[j] = tmp;
60 }
61 }
62 }
63
64 int maxSaved = -1;
65 int bestNode = initial[0];
66
67 // Determine best node to remove
68 for (int i = 0; i < initialSize; i++) {
69 int node = initial[i];
70 int root = find(parent, node);
71 if (infectedCount[root] == 1) {
72 int saved = 0;
73 for (int j = 0; j < graphSize; j++) {
74 if (find(parent, j) == root) {
75 saved++;
76 }
77 }
78 if (saved > maxSaved) {
79 maxSaved = saved;
80 bestNode = node;
81 }
82 }
83 }
84
85 free(parent);
86 free(rank);
87 free(infectedCount);
88
89 return bestNode;
90}This C implementation uses a union-find structure to group nodes and determine connected components. Arrays parent and rank manage the nodes, and a loop runs through the graph to union connected nodes. The implementation finds infections in each group, determines the best node to remove, ensuring maximum infections are saved.
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.
1function minMalwareSpread(graph, initial)
In JavaScript, this code employs DFS for component discovery. It tallies infective presence and decides best removal via infective reduction effect, while preserving ordering for minimum index assurance.