Reorder Routes to Make All Paths Lead to the City Zero

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int,int>>> adj(n);
        for (auto& c : connections) {
            adj[c[0]].push_back({c[1], 1});  // original direction
            adj[c[1]].push_back({c[0], 0});  // reverse
        }
        vector<bool> seen(n, false);
        seen[0] = true;
        queue<int> q;
        q.push(0);
        int flips = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto [v, isOriginal] : adj[u]) {
                if (seen[v]) continue;
                seen[v] = true;
                flips += isOriginal;
                q.push(v);
            }
        }
        return flips;
    }
};

func minReorder(n int, connections [][]int) int {
    type edge struct{ to, orig int }
    adj := make([][]edge, n)
    for _, c := range connections {
        adj[c[0]] = append(adj[c[0]], edge{c[1], 1})
        adj[c[1]] = append(adj[c[1]], edge{c[0], 0})
    }
    seen := make([]bool, n)
    seen[0] = true
    q := []int{0}
    flips := 0
    for len(q) > 0 {
        u := q[0]
        q = q[1:]
        for _, e := range adj[u] {
            if seen[e.to] {
                continue
            }
            seen[e.to] = true
            flips += e.orig
            q = append(q, e.to)
        }
    }
    return flips
}

from typing import List
from collections import deque

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
        for a, b in connections:
            adj[a].append((b, 1))  # original direction
            adj[b].append((a, 0))  # reverse
        seen = [False] * n
        seen[0] = True
        q = deque([0])
        flips = 0
        while q:
            u = q.popleft()
            for v, is_original in adj[u]:
                if seen[v]:
                    continue
                seen[v] = True
                flips += is_original
                q.append(v)
        return flips

function minReorder(n, connections) {
    const adj = Array.from({ length: n }, () => []);
    for (const [a, b] of connections) {
        adj[a].push([b, 1]); // original direction
        adj[b].push([a, 0]); // reverse
    }
    const seen = new Array(n).fill(false);
    seen[0] = true;
    const q = [0];
    let head = 0;
    let flips = 0;
    while (head < q.length) {
        const u = q[head++];
        for (const [v, isOriginal] of adj[u]) {
            if (seen[v]) continue;
            seen[v] = true;
            flips += isOriginal;
            q.push(v);
        }
    }
    return flips;
}

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<int[]>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] c : connections) {
            adj[c[0]].add(new int[]{c[1], 1}); // original direction
            adj[c[1]].add(new int[]{c[0], 0}); // reverse
        }
        boolean[] seen = new boolean[n];
        seen[0] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        int flips = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] e : adj[u]) {
                int v = e[0], isOriginal = e[1];
                if (seen[v]) continue;
                seen[v] = true;
                flips += isOriginal;
                q.offer(v);
            }
        }
        return flips;
    }
}

function minReorder(n: number, connections: number[][]): number {
    const adj: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
    for (const [a, b] of connections) {
        adj[a].push([b, 1]); // original direction
        adj[b].push([a, 0]); // reverse
    }
    const seen: boolean[] = new Array<boolean>(n).fill(false);
    seen[0] = true;
    const q: number[] = [0];
    let head = 0;
    let flips = 0;
    while (head < q.length) {
        const u = q[head++];
        for (const [v, isOriginal] of adj[u]) {
            if (seen[v]) continue;
            seen[v] = true;
            flips += isOriginal;
            q.push(v);
        }
    }
    return flips;
}