DAG

DAG

文章目录

• • 851.喧闹和富有
  • • 暴力BFS超时
    • DFS
    • 拓扑排序

851.喧闹和富有 暴力BFS超时

class Solution(object):
    def loudAndRich(self, richer, quiet):
        # DAG
        edges = defaultdict(list)
        for r in richer:
            edges[r[1]].append(r[0])
        num = len(quiet)
        ans = [0] * num
        for i in range(num):
            if i not in edges:
                ans[i] = i
            else:
                # BFS
                q = deque(edges[i])
                mn, node = quiet[i], i
                while q:
                    cur = q.popleft()
                    if cur in edges:
                        for temp in edges[cur]:
                            q.append(temp)
                    if quiet[cur] < mn:
                        mn = quiet[cur]
                        node = cur
                ans[i] = node
        return ans

时间复杂度： O ( m n ) O(mn) O(mn)，往上走

---

DFS

• 建DAG，同样的没钱指向有钱

• DFS，邻居们的钱我不全拿，我只拿最少的。

• 注意，不要重复S

class Solution(object):
    def loudAndRich(self, richer, quiet):
        # DAG
        edges = defaultdict(list)
        for r in richer:
            edges[r[1]].append(r[0])
        n = len(quiet)
        ans = [-1] * n
        
        # DFS
        def dfs(x):
            # base
            if ans[x] != -1:
                return 
            ans[x] = x
            for y in edges[x]:
                dfs(y)
                if quiet[ans[x]] > quiet[ans[y]]:
                    ans[x] = ans[y]

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

执行用时：56 ms, 在所有 Python 提交中击败了66.67%的用户
内存消耗：19.9 MB, 在所有 Python 提交中击败了66.67%的用户

时间复杂度： O ( m + n ) O(m+n) O(m+n)
空间复杂度： O ( m + n ) O(m+n) O(m+n)

---

拓扑排序

• 什么是拓扑排序？Bilibili，你就知道。
• 还是建DAG，这次是有钱指向没钱
• 拓扑排序，和BFS相似

class Solution(object):
    def loudAndRich(self, richer, quiet):
        num = len(quiet)
        # DAG  rich ——> poor
        edges = defaultdict(list)
        inDegree = [0] * num
        for r in richer:
            edges[r[0]].append(r[1])
            inDegree[r[1]] += 1
        ans = [i for i in range(num)]
        # Topological Sorting
        q = deque([i for i in range(num) if inDegree[i] == 0])
        while q:
            x = q.popleft()
            for y in edges[x]:
                if quiet[ans[y]] > quiet[ans[x]]:
                    ans[y] = ans[x]
                inDegree[y] -= 1
                if inDegree[y] == 0:
                    q.append(y)
        return ans

执行用时：68 ms, 在所有 Python 提交中击败了11.11%的用户
内存消耗：20.1 MB, 在所有 Python 提交中击败了33.33%的用户

时间复杂度： O ( m + n ) O(m+n) O(m+n)，没有重复计算
空间复杂度： O ( m + n ) O(m+n) O(m+n)，点和边