https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero

Let us put all the edges into adjacency list twice, one with weight 1 and one with weight -1 with oppisite direction. Then what we do is just traverse our graph using usual dfs, and when we try to visit some neighbour, we check if this edge is usual or reversed.

Complexity is O(V+E), because we traverse our graph only once.

class Solution:
    def dfs(self, start):
        self.visited[start] = 1
        for neib in self.adj[start]:
            if self.visited[neib[0]] == 0:
                if neib[1] == 1:
                    self.count += 1
                self.dfs(neib[0])
    
    def minReorder(self, n, connections):
        self.visited = [0] * n
        self.adj = defaultdict(list) 
        self.count = 0
        for i, j in connections:
            self.adj[i].append([j,1])
            self.adj[j].append([i,-1])

        self.dfs(0)
        return self.count

If you like the solution, you can upvote it on leetcode discussion section: Problem 1466