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

[songyy5517]

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow. Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi. This year, there will be a big event in the capital (city 0), and many people want to travel to this city. Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed. It's guaranteed that each city can reach city 0 after reorder.

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Intuition The problem can be converted into finding the number of edges from parent to child with node 0 as the root. Therefore, we can travarse the whole graph from 0 using DFS, and calculate the number of edges from parent to child. To determine the direction of an edge, we need to define a nested arraylist to store all edges of each node, where reverse edges are set to negative (its opposite number). Therefore, the solution include three steps in general: 1. Transform the graph into a tree, that is, convert all the directed edges into undirected edges in the graph; 2. Travarse the graph from node 0, and identify negative paths by comparing the direction of each edge and its original direction; 3. Compute the total number of nagative edges.

[songyy5517]

Approach: DFS, convert the graph to a tree

1. Exception handling;
2. Define variables & Initialization:
   • isVisited: the visit array;
   • ArrayList<Integer>[] adj: store all adjacent nodes of each node. For each element in connections, we add the corresponding node value to adj according to the direction of edge;
   • num: the number of paths from parent to child (negative edge).
3. Travarse the whole graph using DFS from node 0: （1）Recursion exit: the node is already visited; （2）Update the visit array; （3）Check all the adjacent nodes of the current node adj[idx]:
   • If the adjacent node is not visited, and it can form a negative node with the current node, then update num and perform DFS on this adjacent node.
4. Return num.

Complexity Analysis

• Time complexity: $O(N)$ , creating the adjacent arraylist takes $O(N)$ time, and travarsing the whole graph using DFS also takes $O(N)$ time.
• Space complexity: $O(N)$ , additionally define a visit array and a ArrayList which take up $O(N)$ space, the recursion depth of DFS is $N$ in the worst case. (Why is the space of ArrayList<Integer>[] $O(N)$ ?)

[songyy5517]

class Solution {
    int num = 0;
    public int minReorder(int n, int[][] connections) {
        // 思路：图转换成树，DFS
        // 1. 异常处理
        if (connections == null)
            return 0;

        // 2. 有向图转换成无向图
        ArrayList<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++)
            adj[i] = new ArrayList();

        for (int i = 0; i < connections.length; i++){
            adj[connections[i][0]].add(connections[i][1]);
            adj[connections[i][1]].add(-connections[i][0]);
        }

        // 3. DFS
        boolean[] isVisited = new boolean[n];
        DFS(adj, isVisited, 0);

        return num;
    }

    void DFS(ArrayList<Integer>[] adj, boolean[] isVisited, int index){
        // 递归出口
        if (isVisited[index])
            return ;

        // 处理当前节点
        isVisited[index] = true;
        for (int neighbor : adj[index]){
            int neighbor_abs = Math.abs(neighbor);
            if (neighbor > 0 && !isVisited[neighbor])
                num ++;
            DFS(adj, isVisited, neighbor_abs);
        }
    }
}

[songyy5517]

2024/6/19 2024/6/21

• num++ & !isVisted