1466. Reorder Routes to Make All Paths Lead to The City Zero - Explanation

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        edges = {(a, b) for a, b in connections}
        neighbors = {city: [] for city in range(n)}
        visit = set()
        changes = 0

        for a, b in connections:
            neighbors[a].append(b)
            neighbors[b].append(a)

        def dfs(city):
            nonlocal changes
            visit.add(city)
            for neighbor in neighbors[city]:
                if neighbor in visit:
                    continue
                if (neighbor, city) not in edges:
                    changes += 1
                dfs(neighbor)

        dfs(0)
        return changes

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for u, v in connections:
            adj[u].append(v)
            adj[v].append(-u)

        def dfs(node, parent):
            changes = 0
            for nei in adj[node]:
                if abs(nei) == parent:
                    continue
                changes += dfs(abs(nei), node) + (nei > 0)
            return changes

        return dfs(0, -1)

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for u, v in connections:
            adj[u].append((v, 1))
            adj[v].append((u, 0))

        visit = [False] * n
        queue = deque([0])
        visit[0] = True
        changes = 0

        while queue:
            node = queue.popleft()
            for neighbor, isForward in adj[node]:
                if not visit[neighbor]:
                    visit[neighbor] = True
                    changes += isForward
                    queue.append(neighbor)
        return changes