Quora 无向图任务

Question

我有下一个编码任务：https://www.hackerrank.com/contests/quora-haqathon/challenges/latedquestions/problem

尝试使用DFS以最少的计算来解决它：

    fun solution(n: Int, t: MutableList<Int>, edges: MutableList<MutableList<Int>>): Int {
    val graph = mutableMapOf<Int, List<Int>>()
    edges.forEach {
        val from = it[0]
        val to = it[1]

        graph.computeIfPresent(from) { _, v -> v + to }
        graph.putIfAbsent(from, listOf(to))

        graph.computeIfPresent(to) { _, v -> v + from }
        graph.putIfAbsent(to, listOf(from))
    }

    var visited = BooleanArray(n)
    fun dfs(node: Int): Double {
        if (visited[node]) return 0.0
        visited[node] = true

        val childNodes = graph[node] ?: listOf<Int>()
        if (childNodes.size == 0)
            return t[node].toDouble()

        var sum = 0.0
        childNodes.forEach { v ->
            sum += dfs(v)
        }
        return t[node] + (sum / childNodes.size.toDouble())
    }

    var minEdge = 0
    var time = Double.MAX_VALUE
    for (i in 0 until n) {
        var res = dfs(i)
        if (res < time) {
            time = res
            minEdge = i
        }
        visited = BooleanArray(n)
    }

    return minEdge
}

不幸的是，我的解决方案有一些失败的测试用例，我不知道这里出了什么问题。你能帮我在这里找到一个逻辑问题吗>

Answer 1

我的代码有两个问题：

1. 我不应该计算每次迭代访问的边
2. 如果访问节点则不删除 0

fun solution(n: Int, t: MutableList<Int>, edges: MutableList<MutableList<Int>>): Int {
    val graph = mutableMapOf<Int, List<Int>>()
    edges.forEach {
        val from = it[0]
        val to = it[1]
        
        graph.computeIfPresent(from) { _, v -> v + to }
        graph.putIfAbsent(from, listOf(to))
        
        graph.computeIfPresent(to) { _, v -> v + from }
        graph.putIfAbsent(to, listOf(from))
    }
    
    var visited = BooleanArray(n)
    fun dfs(node: Int): Double {
        visited[node] = true
        
        val childNodes = graph[node]?.filter { !visited[it] } ?: listOf<Int>()
        if (childNodes.size == 0)
            return t[node].toDouble()
        
        var sum = 0.0
        childNodes.forEach { v ->
            sum += dfs(v)
        }
        
        return t[node] + (sum / childNodes.size.toDouble())
    }
    
    val times = DoubleArray(n)
    for (i in 0 until n) {
        times[i] = dfs(i)
        visited = BooleanArray(n)
    }
    
    var minEdge = 0
    var time = Double.MAX_VALUE
    for (i in 0 until n) {
        var res = dfs(i)
        if (res < time) {
            time = res 
            minEdge = i
        }
        visited = BooleanArray(n)
    }
    
    return minEdge
}