Сложность: hard
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
👨💻 Алгоритм:
1⃣Определить компоненты связности в графе.
Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов.
2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.
3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.
😎 Решение:
def minMalwareSpread(graph, initial):
n = len(graph)
def dfs(node, visited):
stack = [node]
while stack:
u = stack.pop()
for v in range(n):
if graph[u][v] == 1 and v not in visited:
visited.add(v)
stack.append(v)
components = []
visited = set()
for i in range(n):
if i not in visited:
component = set()
dfs(i, component)
components.append(component)
visited.update(component)
infected_in_component = [0] * len(components)
node_to_component = {}
for idx, component in enumerate(components):
for node in component:
node_to_component[node] = idx
if node in initial:
infected_in_component[idx] += 1
min_infected = float('inf')
result_node = min(initial)
for node in initial:
component_idx = node_to_component[node]
if infected_in_component[component_idx] == 1:
component_size = len(components[component_idx])
if component_size < min_infected or (component_size == min_infected and node < result_node):
min_infected = component_size
result_node = node
return result_node
Ставь 👍 и забирай 📚 Базу знаний