851. 喧闹和富有

解题思路

依题意richer可以很容易画出有向无环图，基于图做DFS即可。基于result结果组数可以做剪枝。

代码

func solve(i int, graph *[][]int, result *[]int, quiet *[]int) (int, int){
    if len((*graph)[i]) == 0{
        (*result)[i] = i
        return i, (*quiet)[i]
    }

    if (*result)[i] != 0{
        return (*result)[i], (*quiet)[(*result)[i]]  // 关键，不是读本数的quiet而是读本数对应result的quiet
    }

    min_val := (*quiet)[i]
    min_i := i
    for _, next_i := range (*graph)[i]{
        idx, val := solve(next_i, graph, result, quiet)
        if val < min_val{
            min_val = val
            min_i = idx
        }
    }
    return min_i, min_val

}

func loudAndRich(richer [][]int, quiet []int) []int {
    graph := make([][]int, len(quiet), len(quiet))
    result := make([]int, len(quiet), len(quiet))

    for _, m := range richer{
        graph[m[1]] = append(graph[m[1]], m[0])
    }

    for i := range quiet{  // only index
        idx, _ := solve(i, &graph, &result, &quiet)
        result[i] = idx
    }

    return result

}