LeetCode之Minimize Malware Spread

问题：

image

方法：
主要是通过DFS遍历所有节点被移除后的M值，然后通过着色法记录走过的节点优化时间复杂度。

具体实现：

class MinimizeMalwareSpreadII {
    fun minMalwareSpread(graph: Array<IntArray>, initial: IntArray): Int {
        var M = graph.size
        var node = initial[0]
        for (virusRemove in initial) {
            val nodes = IntArray(graph.size) { 0 }
            for (virus in initial) {
                if (virus == virusRemove) {
                    continue
                }
                dfs(graph, virusRemove, nodes, virus)
            }
            if (nodes.sum() < M || (nodes.sum() == M && virusRemove < node)) {
                M = nodes.sum()
                node = virusRemove
            }
        }
        return node
    }

    private fun dfs(graph: Array<IntArray>, virusRemove: Int, nodes: IntArray, virus: Int) {
        if (nodes[virus] == 1) {
            return
        } else {
            nodes[virus] = 1
            for (index in graph[virus].indices) {
                if (graph[virus][index] == 1 && index != virusRemove) {
                    dfs(graph, virusRemove, nodes, index)
                }
            }
        }
    }
}

fun main(args: Array<String>) {
    val graph = arrayOf(intArrayOf(1, 1, 0), intArrayOf(1, 1, 1), intArrayOf(0, 1, 1))
    val initial = intArrayOf(0, 1)
    val minimizeMalwareSpreadII = MinimizeMalwareSpreadII()
    println(minimizeMalwareSpreadII.minMalwareSpread(graph, initial))
}

有问题随时沟通

具体代码实现可以参考Github