Maximum Total Importance of Roads

Info

You don’t have to do dfs. You just use the fact that the highest priority should be given to those vertices with the most edges.

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        max_heap = [0] * n
        for u, v in roads:
            max_heap[u] -= 1
            max_heap[v] -= 1
        heapify(max_heap)
 
        res = 0
        while max_heap:
            largest = -heappop(max_heap)
            res += largest * n
            n -= 1
        return res

---

References

https://leetcode.com/problems/maximum-total-importance-of-roads/