PYTHON: Priority Queue with Topological ordering
Build a graph based on two given arrays\nCount each node\'s indegree respectively\n\nConstruct a Priority Queue that maintains the current minimum sum.\nThe rea
Build a graph based on two given arrays\nCount each node\'s indegree respectively\n\nConstruct a Priority Queue that maintains the current minimum sum.\nThe reason is that as we perform indegree - 1 for each node afterward, we exhausted the count of indegree by the minimum previous sum path. At the end, when a given node\'s indegree == 0, we left the maximum previous sum to the current node. Hence, we push the maximum sum including the current node\'s value to the PQ, which maintains the maximum value for each node after.\n\nFor example:\n```\n4 - > 5  -> 8 \n4 -> 6 -> 8\n```\n4 has 0 indegree, it will be pushed to pq first as (4,4)  (cur_sum, node)\nthen we examine 5 and 6, both are 4\'s neighbors. take indegree - 1, resulting both indegree == 0. we need to push\n(9, 5) and (10, 6) to PQ\n\nNotice here 8 has indegree = 2, coming from 5 and 6. because PQ always pop the smallest sum, (9,5) will first be poped and we start to examine 8, which cause indegree - 1 == 1. Since we are not reaching 0, **ignore** \n**We are ignoring the minimum sum path!** Later when (10,6) poped up, 10 is the current maxium sum path to node 8. we can now add (18,8) to the PQ. \n\n**Hence, we maintain the maximum path by ignoring the smaller sum path altogether. The reason is we are using the PQ that prioritize the smallest sum first**\n\nCode:\n```\n\n    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n        # build graph: topological sort\n        s = set(nums1+nums2)\n        indegree = {n:0 for n in s}\n        g = collections.defaultdict(list)\n        for i in range(1,len(nums1)):\n            indegree[nums1[i]] += 1\n            g[nums1[i-1]].append(nums1[i])\n        if nums1[-1] not in g:\n            g[nums1[-1]] = []\n            \n        for i in range(1,len(nums2)):\n            indegree[nums2[i]] +=1\n            g[nums2[i-1]].append(nums2[i])\n        if nums2[-1] not in g:\n            g[nums2[-1]] = []\n            \n\n        pq = [(key,key) for key,val in indegree.items() if val == 0]\n        heapq.heapify(pq)\n        ans = 0\n        while pq: \n            cur_sum, node = heapq.heappop(pq)             # always pop the current minimum sum\n            ans = cur_sum\n            for nei in g[node]:                         \n                indegree[nei] -= 1                        # exhaust indegree for the smaller sum\n                if indegree[nei] == 0:                    # guarantee the largest sum cause the nei\'s indegree to 0\n                    heapq.heappush(pq, (cur_sum+nei, nei)) # hence, we maintain the largest sum to the end\n\n        \n        return ans % (10**9+7)\n                \n\n\n```\n
[]