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

class Solution {
    private static class Edge {
        private final int from;
        private final int to;
        private final int direction;

        public Edge(int from, int to, int direction) {
            this.from = from;
            this.to = to;
            this.direction = direction;
        }
    }

    public int minReorder(int n, int[][] connections) {
        List<List<Edge>> nodeToEdgeListMap = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nodeToEdgeListMap.add(new ArrayList<>());
        }
        for (int[] connection : connections) {
            int nodeA = connection[0], nodeB = connection[1];
            nodeToEdgeListMap.get(nodeA).add(new Edge(nodeA, nodeB, 1));
            nodeToEdgeListMap.get(nodeB).add(new Edge(nodeB, nodeA, 0));
        }

        return dfs(0, -1, nodeToEdgeListMap);
    }

    private int dfs(int from, int parent, List<List<Edge>> nodeToEdgeListMap) {
        int res = 0;

        // 遍历当前起点所有的边
        for (Edge edge : nodeToEdgeListMap.get(from)) {
            if (edge.to == parent) {
                // 防止走回头路
                continue;
            }

            res += edge.direction + dfs(edge.to, from, nodeToEdgeListMap); // 因为我们是从 0 为起点去进行 DFS 搜索，所以正向的边都需要加 1，因为题目找的是从其他城市前往城市 0 时需要变更方向的路线数
        }

        return res;
    }
}

References

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