Kotlin | 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 {
    fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
        val n = graph.size
        val visited = mutableSetOf<Int>()
        val components = mutableListOf<MutableSet<Int>>()
        
        fun dfs(node: Int) {
            val stack = mutableListOf(node)
            val component = mutableSetOf<Int>()
            while (stack.isNotEmpty()) {
                val u = stack.removeAt(stack.lastIndex)
                if (u !in visited) {
                    visited.add(u)
                    component.add(u)
                    for (v in 0 until n) {
                        if (graph[u][v] == 1 && v !in visited) {
                            stack.add(v)
                        }
                    }
                }
            }
            components.add(component)
        }
        
        for (i in 0 until n) {
            if (i !in visited) {
                dfs(i)
            }
        }
        
        val infectedInComponent = IntArray(components.size)
        val nodeToComponent = IntArray(n) { -1 }
        
        for ((idx, component) in components.withIndex()) {
            for (node in component) {
                nodeToComponent[node] = idx
                if (node in initial) {
                    infectedInComponent[idx]++
                }
            }
        }
        
        var minInfected = Int.MAX_VALUE
        var resultNode = initial.minOrNull()!!
        
        for (node in initial) {
            val componentIdx = nodeToComponent[node]
            if (infectedInComponent[componentIdx] == 1) {
                val componentSize = components[componentIdx].size
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize
                    resultNode = node
                }
            }
        }
        
        return resultNode
    }
}

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

Please open Telegram to view this post