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

[fockspaces]

stage 1: create map

1. create src_to_dest, dest_to_src for lookup

stage 2: BFS take node 0 as source first, strat BFS traverse

1. if node is pointed by source, edges += 1, then add to queue
2. if node point to source, add it to queue wihout adding edges
3. we should use reached set to avoid duplicated adding node

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        queue = [0]
        reached = set()
        edges = 0
        src_to_dest, dest_to_src = {}, {}
        for src, dest in connections:
            src_to_dest[src] = src_to_dest.get(src, []) + [dest]
            dest_to_src[dest] = dest_to_src.get(dest, []) + [src]
        while queue:
            target = queue.pop(0)
            for dest in src_to_dest.get(target, []):
                if dest not in reached:
                    edges += 1
                    queue.append(dest)
            for src in dest_to_src.get(target, []):
                if src not in reached:
                    queue.append(src)
            reached.add(target)
        return edges