1466. Reorder Routes to Make All Paths Lead to the City Zero

这道题很厉害，contest没有做出来，用inorder degree的思路（topological) 不对

use pos/neg to determine the direction

1 -> 2

[1].add(2)

[2].add(-1)

from collections import defaultdict
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj_list = defaultdict(list)
        for con in connections:
            a,b = con
            adj_list[a].append(b)
            adj_list[b].append(-a)
        self.visited = [0] * n
        def dfs(start):
            res = 0
            for nxt in adj_list[start]:
                if self.visited[abs(nxt)] == 1:
                    continue
                if nxt > 0:
                    res+=1
                self.visited[abs(nxt)] = 1
                res += dfs(abs(nxt))
            return res
        self.visited[0] = 1
        return dfs(0)

from collections import defaultdict
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj_list = defaultdict(list)
        for con in connections:
            a,b = con
            adj_list[a].append(b)
            adj_list[b].append(-a)
        visited = [0] * n
        def dfs(start,vis):
            res = 0
            for nxt in adj_list[start]:
                if vis[abs(nxt)] == 1:
                    continue
                if nxt > 0:
                    res+=1
                vis[abs(nxt)] = 1
                res += dfs(abs(nxt),vis)
            return res
        visited[0] = 1
        return dfs(0,visited)