928. Minimize Malware Spread II
leetcode hard
#array#csharp#graph#hard#hash-table#leetcode#linked-list#matrix#stack
Task
Вам дана сеть из 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
C# solution
matched/originalpublic class Solution {
public int MinMalwareSpread(int[][] graph, int[] initial) {
int n = graph.Length;
var visited = new HashSet<int>();
var components = new List<HashSet<int>>();
void Dfs(int node) {
var stack = new Stack<int>();
stack.Push(node);
var component = new HashSet<int>();
while (stack.Count > 0) {
int u = stack.Pop();
if (!visited.Contains(u)) {
visited.Add(u);
component.Add(u);
for (int v = 0; v < n; v++) {
if (graph[u][v] == 1 && !visited.Contains(v)) {
stack.Push(v);
}
}
}
}
components.Add(component);
}
for (int i = 0; i < n; i++) {
if (!visited.Contains(i)) {
Dfs(i);
}
}
int[] infectedInComponent = new int[components.Count];
int[] nodeToComponent = new int[n];
Array.Fill(nodeToComponent, -1);
for (int idx = 0; idx < components.Count; idx++) {
var component = components[idx];
foreach (int node in component) {
nodeToComponent[node] = idx;
if (Array.IndexOf(initial, node) >= 0) {
infectedInComponent[idx]++;
}
}
}
int minInfected = int.MaxValue;
int resultNode = initial.Min();
foreach (int node in initial) {
int componentIdx = nodeToComponent[node];
if (infectedInComponent[componentIdx] == 1) {
int componentSize = components[componentIdx].Count;
if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
minInfected = componentSize;
resultNode = node;
}
}
}
return resultNode;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MinMalwareSpread(int[][] graph, vector<int>& initial) {
int n = graph.size();
var visited = new HashSet<int>();
var components = new List<HashSet<int>>();
void Dfs(int node) {
var stack = new stack<int>();
stack.push(node);
var component = new HashSet<int>();
while (stack.size() > 0) {
int u = stack.pop();
if (!visited.Contains(u)) {
visited.push_back(u);
component.push_back(u);
for (int v = 0; v < n; v++) {
if (graph[u][v] == 1 && !visited.Contains(v)) {
stack.push(v);
}
}
}
}
components.push_back(component);
}
for (int i = 0; i < n; i++) {
if (!visited.Contains(i)) {
Dfs(i);
}
}
vector<int>& infectedInComponent = new int[components.size()];
vector<int>& nodeToComponent = new int[n];
Array.Fill(nodeToComponent, -1);
for (int idx = 0; idx < components.size(); idx++) {
var component = components[idx];
foreach (int node in component) {
nodeToComponent[node] = idx;
if (Array.IndexOf(initial, node) >= 0) {
infectedInComponent[idx]++;
}
}
}
int minInfected = int.MaxValue;
int resultNode = initial.Min();
foreach (int node in initial) {
int componentIdx = nodeToComponent[node];
if (infectedInComponent[componentIdx] == 1) {
int componentSize = components[componentIdx].size();
if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
minInfected = componentSize;
resultNode = node;
}
}
}
return resultNode;
}
}Java solution
matched/originalimport java.util.*;
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
Set<Integer> visited = new HashSet<>();
List<Set<Integer>> components = new ArrayList<>();
void dfs(int node) {
Stack<Integer> stack = new Stack<>();
stack.push(node);
Set<Integer> component = new HashSet<>();
while (!stack.isEmpty()) {
int u = stack.pop();
if (!visited.contains(u)) {
visited.add(u);
component.add(u);
for (int v = 0; v < n; v++) {
if (graph[u][v] == 1 && !visited.contains(v)) {
stack.push(v);
}
}
}
}
components.add(component);
}
for (int i = 0; i < n; i++) {
if (!visited.contains(i)) {
dfs(i);
}
}
int[] infectedInComponent = new int[components.size()];
int[] nodeToComponent = new int[n];
Arrays.fill(nodeToComponent, -1);
for (int idx = 0; idx < components.size(); idx++) {
Set<Integer> component = components.get(idx);
for (int node : component) {
nodeToComponent[node] = idx;
if (Arrays.stream(initial).anyMatch(x -> x == node)) {
infectedInComponent[idx]++;
}
}
}
int minInfected = Integer.MAX_VALUE;
int resultNode = Arrays.stream(initial).min().getAsInt();
for (int node : initial) {
int componentIdx = nodeToComponent[node];
if (infectedInComponent[componentIdx] == 1) {
int componentSize = components.get(componentIdx).size();
if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
minInfected = componentSize;
resultNode = node;
}
}
}
return resultNode;
}
}JavaScript solution
matched/originalfunction minMalwareSpread(graph, initial) {
const n = graph.length;
function dfs(node, visited, component) {
const stack = [node];
while (stack.length > 0) {
const u = stack.pop();
component.push(u);
for (let v = 0; v < n; v++) {
if (graph[u][v] === 1 && !visited.has(v)) {
visited.add(v);
stack.push(v);
}
}
}
}
const components = [];
const visited = new Set();
for (let i = 0; i < n; i++) {
if (!visited.has(i)) {
const component = [];
visited.add(i);
dfs(i, visited, component);
components.push(component);
}
}
const infectedInComponent = new Array(components.length).fill(0);
const nodeToComponent = new Map();
components.forEach((component, idx) => {
for (const node of component) {
nodeToComponent.set(node, idx);
}
});
for (const node of initial) {
const componentIdx = nodeToComponent.get(node);
infectedInComponent[componentIdx]++;
}
initial.sort((a, b) => a - b);
let minInfected = Infinity;
let resultNode = initial[0];
for (const node of initial) {
const componentIdx = nodeToComponent.get(node);
if (infectedInComponent[componentIdx] === 1) {
const componentSize = components[componentIdx].length;
if (componentSize < minInfected || (componentSize === minInfected && node < resultNode)) {
minInfected = componentSize;
resultNode = node;
}
}
}
return resultNode;
}Python solution
matched/originaldef 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_nodeGo solution
matched/originalpackage main
func minMalwareSpread(graph [][]int, initial []int) int {
n := len(graph)
visited := make(map[int]struct{})
components := []map[int]struct{}{}
var dfs func(int)
dfs = func(node int) {
stack := []int{node}
component := make(map[int]struct{})
for len(stack) > 0 {
u := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if _, ok := visited[u]; !ok {
visited[u] = struct{}{}
component[u] = struct{}{}
for v := 0; v < n; v++ {
if graph[u][v] == 1 {
if _, ok := visited[v]; !ok {
stack = append(stack, v)
}
}
}
}
}
components = append(components, component)
}
for i := 0; i < n; i++ {
if _, ok := visited[i]; !ok {
dfs(i)
}
}
infectedInComponent := make([]int, len(components))
nodeToComponent := make([]int, n)
for i := range nodeToComponent {
nodeToComponent[i] = -1
}
for idx, component := range components {
for node := range component {
nodeToComponent[node] = idx
for _, init := range initial {
if node == init {
infectedInComponent[idx]++
}
}
}
}
minInfected := int(^uint(0) >> 1)
resultNode := initial[0]
for _, node := range initial {
componentIdx := nodeToComponent[node]
if infectedInComponent[componentIdx] == 1 {
componentSize := len(components[componentIdx])
if componentSize < minInfected || (componentSize == minInfected && node < resultNode) {
minInfected = componentSize
resultNode = node
}
}
}
return resultNode
}Explanation
Algorithm
Определить компоненты связности в графе.
Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов.
Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.
Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.
😎