重新规划路线

Problem: 1466. 重新规划路线

基本思路

可将节点两个部分：

第一部分保证节点到达 节点。

第二部分不能保证到达 节点。

使用队列保存当前状态下可能连接有第二部分的第一部分节点，需要更改路径的次数设为。

考虑下图：

初始状态下，。

进行以下操作：

取出队头节点，对节点进行深搜：分别来到节点，说明节点的路径不能到达 节点，此时需要把路径反向的次数为。

对于搜索过程中每条路径的节点，由于指向该节点的节点是肯定能到达节点（属于第一部分），但不能保证 节点连接的其它未被访问的节点 能够到达（属于第二部分），故将节点入队（是可能连接有第二部分的第一部分节点）。

此时。

继续执行以上操作：。

此时队列为空，需要更改路径的次数为。

代码

Java


class Solution {
    @SuppressWarnings("unchecked")
    public int minReorder(int n, int[][] connections) {
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < connections.length; i++) {
            graph[connections[i][0]].add(connections[i][1]);
            graph[connections[i][1]].add(-connections[i][0]);
        }

        int ans = 0;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            ans += dfs(graph, queue, visited, queue.poll()) - 1;
        }
        return ans;
    }
    int dfs(List<Integer>[] graph, Queue<Integer> queue, boolean[] visited, int node) {
        int count = 1;
        visited[node] = true;
        for (int next : graph[node]) {
            if (next > 0) {
                if (!visited[next]) {
                    count += dfs(graph, queue, visited, next);
                }
            } else if (!visited[-next]) {
                queue.offer(-next);
            }
        }
        return count;
    }
}

Python3


class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for connection in connections:
            graph[connection[0]].append(connection[1])
            graph[connection[1]].append(-connection[0])

        ans = 0
        visited = [False for _ in range(n)]
        queue = deque()
        queue.append(0)
        while len(queue) > 0:
            ans += self.dfs(graph, queue, visited, queue.popleft()) - 1
        return ans

    def dfs(self, graph: List[List[int]], queue: deque, visited: List[bool], node: int) -> int:
        count = 1
        visited[node] = True
        for nextNode in graph[node]:
            if nextNode > 0:
                if not visited[nextNode]:
                    count += self.dfs(graph, queue, visited, nextNode)
            elif not visited[-nextNode]:
                queue.append(-nextNode)
        return count

TypeScript


function minReorder(n: number, connections: number[][]): number {
    const graph: number[][] = new Array(n).fill(0).map(() => new Array());
    for (let i = 0; i < connections.length; i++) {
        graph[connections[i][0]].push(connections[i][1]);
        graph[connections[i][1]].push(-connections[i][0]);
    }

    let ans = 0;
    const visited: boolean[] = new Array(n).fill(false);
    const queue: number[] = [];
    queue.push(0);
    while (queue.length > 0) {
        ans += dfs(graph, queue, visited, queue.shift()!) - 1;
    }
    return ans;
};

function dfs(graph: number[][], queue: number[], visited: boolean[], node: number): number {
    let count = 1;
    visited[node] = true;
    for (let i = 0; i < graph[node].length; i++) {
        let next = graph[node][i];
        if (next > 0) {
            if (!visited[next]) {
                count += dfs(graph, queue, visited, next);
            }
        } else if (!visited[-next]) {
            queue.push(-next);
        }
    }
    return count;
};

JavaScript


/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var minReorder = function(n, connections) {
    const graph = new Array(n).fill(0).map(() => new Array());
    for (let i = 0; i < connections.length; i++) {
        graph[connections[i][0]].push(connections[i][1]);
        graph[connections[i][1]].push(-connections[i][0]);
    }

    let ans = 0;
    const visited = new Array(n).fill(false);
    const queue = [];
    queue.push(0);
    while (queue.length > 0) {
        ans += dfs(graph, queue, visited, queue.shift()) - 1;
    }
    return ans;
};

/**
 * @param {number[][]} graph
 * @param {number[]} queue
 * @param {boolean[]} visited
 * @param {number} node
 * @return {number}
 */
var dfs = function(graph, queue, visited, node) {
    let count = 1;
    visited[node] = true;
    for (let i = 0; i < graph[node].length; i++) {
        let next = graph[node][i];
        if (next > 0) {
            if (!visited[next]) {
                count += dfs(graph, queue, visited, next);
            }
        } else if (!visited[-next]) {
            queue.push(-next);
        }
    }
    return count;
};


public class Solution {
    public int MinReorder(int n, int[][] connections) {
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        for (int i = 0; i < connections.Length; i++) {
            graph[connections[i][0]].Add(connections[i][1]);
            graph[connections[i][1]].Add(-connections[i][0]);
        }

        int ans = 0;
        bool[] visited = new bool[n];
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(0);
        while (queue.Count > 0) {
            ans += Dfs(graph, queue, visited, queue.Dequeue()) - 1;
        }
        return ans;
    }
    int Dfs(List<int>[] graph, Queue<int> queue, bool[] visited, int node) {
        int count = 1;
        visited[node] = true;
        foreach (var next in graph[node]) {
            if (next > 0) {
                if (!visited[next]) {
                    count += Dfs(graph, queue, visited, next);
                }
            } else if (!visited[-next]) {
                queue.Enqueue(-next);
            }
        }
        return count;
    }
}

复杂度分析

时间复杂度：，其中为节点的数量。每个节点最多入队一次，深搜时最多被扩展一次。

空间复杂度：，其中为节点的数量。队列和深搜栈空间不会超过。