C/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⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎

Решение:

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        vector<unordered_set<int>> components;
        unordered_set<int> visited;
        
        auto dfs = [&](int node) {
            stack<int> stk;
            stk.push(node);
            unordered_set<int> component;
            while (!stk.empty()) {
                int u = stk.top();
                stk.pop();
                if (!visited.count(u)) {
                    visited.insert(u);
                    component.insert(u);
                    for (int v = 0; v < n; ++v) {
                        if (graph[u][v] == 1 && !visited.count(v)) {
                            stk.push(v);
                        }
                    }
                }
            }
            components.push_back(component);
        };
        
        for (int i = 0; i < n; ++i) {
            if (!visited.count(i)) {
                dfs(i);
            }
        }
        
        vector<int> infectedInComponent(components.size(), 0);
        vector<int> nodeToComponent(n, -1);
        
        for (int i = 0; i < components.size(); ++i) {
            for (int node : components[i]) {
                nodeToComponent[node] = i;
                if (find(initial.begin(), initial.end(), node) != initial.end()) {
                    infectedInComponent[i]++;
                }
            }
        }
        
        int minInfected = INT_MAX;
        int resultNode = *min_element(initial.begin(), initial.end());
        
        for (int node : 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;
    }
};

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

Please open Telegram to view this post