reorder routes to make all paths lead to city zero

🏠

credit

 1from typing import List
 2from collections import defaultdict
 3
 4class Solution:
 5    def minReorder(self, n: int, connections: List[List[int]]) -> int:
 6        def dfs(u, parent):
 7            self.res += (parent, u) in roads
 8            for v in g[u]:
 9                if v != parent:
10                    dfs(v, u)
11        self.res, roads, g = 0, set(), defaultdict(set)
12        for u, v in connections:
13            roads.add((u, v))
14            g[v].add(u)
15            g[u].add(v)
16        dfs(0, -1)
17        return self.res
18
19s = Solution().minReorder(n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]])
20print(s)