C# | LeetCode

Задача: 928. Minimize Malware Spread II
Сложность: 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⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

public 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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

271 views09:05