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 def __init__(self, size):
3 self.parent = list(range(size))
4 self.rank = [1] * size
5
6 def find(self, node):
7 if self.parent[node] != node:
8 self.parent[node] = self.find(self.parent[node]) # Path compression
9 return self.parent[node]
10
11 def union(self, node1, node2):
12 root1, root2 = self.find(node1), self.find(node2)
13 if root1 != root2:
14 if self.rank[root1] > self.rank[root2]:
15 self.parent[root2] = root1
16 elif self.rank[root1] < self.rank[root2]:
17 self.parent[root1] = root2
18 else:
19 self.parent[root2] = root1
20 self.rank[root1] += 1
21
22class Solution:
23 def minMalwareSpread(self, graph, initial):
24 n = len(graph)
25 uf = UnionFind(n)
26
27 for i in range(n):
28 for j in range(n):
29 if graph[i][j] == 1:
30 uf.union(i, j)
31
32 initial.sort() # Sort nodes to ensure minimum index is picked in ties
33
34 infected_count = [0] * n
35 for node in initial:
36 root = uf.find(node)
37 infected_count[root] += 1
38
39 max_saved = -1
40 best_node = initial[0]
41 for node in initial:
42 root = uf.find(node)
43 if infected_count[root] == 1: # Unique infection in this component
44 saved = sum(1 for i in range(n) if uf.find(i) == root)
45 if saved > max_saved:
46 max_saved = saved
47 best_node = node
48
49 return best_nodeThe solution defines a Union-Find class with find and union methods to manage node groups efficiently. The minMalwareSpread method initiates a Union-Find instance, groups nodes, counts infections per component, sorts initial infections, and finds the best node to remove based on the unique infections that save the most nodes from being infected.
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.
1from collections import defaultdict, deque
2
3
This Python code uses BFS to find connected components and tags them. It processes components comparing infection counts and decides which node removal saves the most others from infection. Initial nodes are sorted for minimum index resolution on equal counts.