Reorder Routes to Make All Paths Lead to the City Zero solution and explanation

def minReorder(n, connections):
    neighbors = {i: [] for i in range(n)}
    for u, v in connections:
        neighbors[u].append((v, 1)) # Indicates original direction u->v
        neighbors[v].append((u, 0)) # Virtual reverse direction

    def dfs(node, parent):
        reorder_count = 0
        for neighbor, direction in neighbors[node]:
            if neighbor == parent:
                continue
            reorder_count += direction + dfs(neighbor, node)
        return reorder_count

    return dfs(0, -1)

function minReorder(n, connections) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        graph[u].push([v, 1]); // original direction
        graph[v].push([u, 0]); // virtual reverse
    }

    function dfs(city, parent) {
        let changes = 0;
        for (const [next, direction] of graph[city]) {
            if (next !== parent) {
                changes += direction + dfs(next, city);
            }
        }
        return changes;
    }

    return dfs(0, -1);
}

import java.util.*;

public int minReorder(int n, int[][] connections) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int i = 0; i < n; i++) {
        graph.put(i, new ArrayList<>());
    }
    for (int[] con : connections) {
        graph.get(con[0]).add(new int[] {con[1], 1}); // direct
        graph.get(con[1]).add(new int[] {con[0], 0}); // reverse
    }

    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[n];
    visited[0] = true;
    queue.add(0);

    int changes = 0;
    while (!queue.isEmpty()) {
        int current = queue.poll();
        for (int[] neighbor : graph.get(current)) {
            if (!visited[neighbor[0]]) {
                visited[neighbor[0]] = true;
                changes += neighbor[1];
                queue.add(neighbor[0]);
            }
        }
    }

    return changes;
}

#include <vector>
#include <queue>

using namespace std;

int minReorder(int n, vector<vector<int>>& connections) {
    vector<vector<pair<int, int>>> graph(n);
    for (const auto& con : connections) {
        graph[con[0]].emplace_back(con[1], 1);
        graph[con[1]].emplace_back(con[0], 0);
    }
    queue<int> q;
    vector<bool> visited(n, false);
    visited[0] = true;
    q.push(0);
    int reorders = 0;

    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (const auto& [next, direction] : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                reorders += direction;
                q.push(next);
            }
        }
    }

    return reorders;
}

function minReorder(n: number, connections: number[][]): number {
    const g: [number, number][][] = Array.from({ length: n }, () => []);
    for (const [a, b] of connections) {
        g[a].push([b, 1]);
        g[b].push([a, 0]);
    }
    const dfs = (a: number, fa: number): number => {
        let ans = 0;
        for (const [b, c] of g[a]) {
            if (b !== fa) {
                ans += c + dfs(b, a);
            }
        }
        return ans;
    };
    return dfs(0, -1);
}

func minReorder(n int, connections [][]int) int {
	g := make([][][2]int, n)
	for _, e := range connections {
		a, b := e[0], e[1]
		g[a] = append(g[a], [2]int{b, 1})
		g[b] = append(g[b], [2]int{a, 0})
	}
	var dfs func(int, int) int
	dfs = func(a, fa int) (ans int) {
		for _, e := range g[a] {
			if b, c := e[0], e[1]; b != fa {
				ans += c + dfs(b, a)
			}
		}
		return
	}
	return dfs(0, -1)
}

impl Solution {
    pub fn min_reorder(n: i32, connections: Vec<Vec<i32>>) -> i32 {
        let mut g: Vec<Vec<(i32, i32)>> = vec![vec![]; n as usize];
        for e in connections.iter() {
            let a = e[0] as usize;
            let b = e[1] as usize;
            g[a].push((b as i32, 1));
            g[b].push((a as i32, 0));
        }
        fn dfs(a: usize, fa: i32, g: &Vec<Vec<(i32, i32)>>) -> i32 {
            let mut ans = 0;
            for &(b, c) in g[a].iter() {
                if b != fa {
                    ans += c + dfs(b as usize, a as i32, g);
                }
            }
            ans
        }
        dfs(0, -1, &g)
    }
}