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

Description

The problem involves determining the minimum number of edges that need to be reversed in a directed graph so that every node is reachable from a starting node (node 0). The graph is represented by n nodes and a list of connections, where each connection is a directed edge between two nodes.

Intuition

The key insight is that if an edge is directed away from the starting node, it might need to be reversed to ensure that all nodes are reachable from node 0. By traversing the graph and counting such edges, we can determine the minimum number of reversals required.

Approach

1. Graph Representation: First, we represent the graph using an adjacency list, where each node points to its connected nodes. We use a positive value for edges that are already correctly oriented and a negative value for edges that might need to be reversed.
2. Depth-First Search (DFS): Starting from node 0, we traverse the graph using DFS. During the traversal, we keep track of visited nodes to avoid cycles and unnecessary computations.
3. Edge Evaluation: For each edge, if the edge is negatively valued (indicating a possible reversal), we increment our reversal count. If the edge is positively valued, we continue the DFS traversal without incrementing the count.
4. Return the Result: The final count after the DFS traversal will give us the minimum number of edges that need to be reversed.

Complexity

Time Complexity:

O(N + E), where N is the number of nodes and E is the number of edges. We traverse each node and edge once.

Space Complexity:

O(N + E), where N is for storing the visited nodes and E is for the adjacency list representing the graph.

Code

C++

class Solution {
public:
    int minReorder(int n, vector>& connections) {
        vector> grid(n);
        vector vis(n, 0);

        for (const auto& conn : connections) {
            int src = conn[0];
            int dest = conn[1];
            grid[src].push_back(-1 * dest);
            grid[dest].push_back(src);
        }

        return solve(grid, 0, vis);
    }

private:
    int solve(vector>& grid, int val, vector& vis) {
        if (vis[val] == 1) {
            return 0;
        }
        int ans = 0;
        vis[val] = 1;
        for (int ele : grid[val]) {
            if (vis[abs(ele)] == 1) {
                continue;
            }
            if (ele < 0) {
                ans += 1;
            }
            ans += solve(grid, abs(ele), vis);
        }
        return ans;
    }
};

Python

class Solution:
    def minReorder(self, n, connections):
        grid = [[] for _ in range(n)]
        vis = [False] * n

        for src, dest in connections:
            grid[src].append(-dest)
            grid[dest].append(src)

        return self.solve(grid, 0, vis)

    def solve(self, grid, val, vis):
        if vis[val]:
            return 0
        ans = 0
        vis[val] = True
        for ele in grid[val]:
            if vis[abs(ele)]:
                continue
            if ele < 0:
                ans += 1
            ans += self.solve(grid, abs(ele), vis)
        return ans

# Example usage:
sol = Solution()
n = 6
connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
print(sol.minReorder(n, connections))

Java

public class Solution {

    private int solve(List> grid, int val, boolean[] vis) {
        if (vis[val]) {
            return 0;
        }
        int ans = 0;
        vis[val] = true;
        for (int ele : grid.get(val)) {
            if (vis[Math.abs(ele)]) {
                continue;
            }
            if (ele < 0) {
                ans += 1;
            }
            ans += solve(grid, Math.abs(ele), vis);
        }
        return ans;
    }

    public int minReorder(int n, int[][] connections) {
        List> grid = new ArrayList<>();
        boolean[] vis = new boolean[n];

        for (int i = 0; i < n; i++) {
            grid.add(new ArrayList<>());
        }

        for (int[] conn : connections) {
            int src = conn[0];
            int dest = conn[1];
            grid.get(src).add(-1 * dest);
            grid.get(dest).add(src);
        }

        return solve(grid, 0, vis);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 6;
        int[][] connections = {{0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}};
        System.out.println(solution.minReorder(n, connections));
    }
}

JavaScript

var minReorder = function (n, connections) {
    let adj = [], grid = [], vis = [], len = connections.length;
    for (let i = 0; i < n; i++) {
        grid.push([]);
        vis[i] = 0;
    }
    for (let i = 0; i < len; i++) {
        let src = connections[i][0];
        let dest = connections[i][1];
        grid[src].push(-1 * dest);
        grid[dest].push(src);
    }
    console.log(grid);
    return solve(grid, 0, vis);
};
function solve(grid, val, vis) {
    if (vis[val] === 1) {
        return 0;
    }
    let ans = 0;
    vis[val] = 1;
    for (let i = 0; i < grid[val].length; i++) {
        let ele = grid[val][i];
        if (vis[Math.abs(ele)] == 1) {
            continue;
        }
        if (ele < 0) {
            ans += 1;
        }
        ans += solve(grid, Math.abs(ele), vis);
    }
    return ans;
}