851.md

851. Loud and Rich

Solution 1 (time O(n), space O(m))

# DFS
class Solution(object):
    def loudAndRich(self, richer, quiet):
        """
        :type richer: List[List[int]]
        :type quiet: List[int]
        :rtype: List[int]
        """
        n = len(quiet)
        info = [[] for _ in range(n)]
        for x, y in richer:
            info[y].append(x)
        ans = [-1 for _ in range(n)]

        def dfs(cur_ind):
            if ans[cur_ind] != -1:
                return
            ans[cur_ind] = cur_ind
            for new_ind in info[cur_ind]:
                dfs(new_ind)
                if quiet[ans[new_ind]] < quiet[ans[cur_ind]]:
                    ans[cur_ind] = ans[new_ind]

        for i in range(n):
            dfs(i)
        return ans