Medium

题目描述

有 n 个城市，编号从 0 到 n-1，以及 n-1 条道路，使得只有一种方式在两个不同的城市之间旅行（这个网络形成一棵树）。去年，交通部决定将道路定向为单向，因为道路太窄了。

道路用连接数组 connections 表示，其中 connections[i] = [ai, bi] 表示从城市 ai 到城市 bi 的一条道路。

今年，首都（城市 0）将举办一个大型活动，许多人想要前往这个城市。

你的任务是重新定向一些道路，使得每个城市都可以访问城市 0。返回需要改变方向的最小边数。

保证每个城市在重新定向后都可以到达城市 0。

示例 1：

输入：n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
输出：3
解释：改变红色边的方向，使得每个节点都可以到达节点 0（首都）。

示例 2：

输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
输出：2
解释：改变红色边的方向，使得每个节点都可以到达节点 0（首都）。

示例 3：

输入：n = 3, connections = [[1,0],[2,0]]
输出：0

提示：

  • 2 <= n <= 5 * 10^4
  • connections.length == n - 1
  • connections[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi

解题思路

这道题的核心思路是将有向图当作无向图处理，从城市 0 开始进行深度优先搜索。

分析过程：

  1. 建图阶段：我们需要构建一个无向图，同时记录原始有向边的方向信息。对于每条边 [a, b]，我们在邻接表中同时添加 a→b 和 b→a 的连接，但需要区分哪些是原始方向的边。

  2. DFS 遍历：从城市 0 开始 DFS 遍历整个树。在遍历过程中，如果我们沿着原始边的方向前进（即从 a 到 b 的原始边），说明这条边的方向是错误的，需要反转，计数器加 1。

  3. 标记策略：可以使用集合或其他方式来标记哪些边是原始方向。一种简单的方法是在构建邻接表时，对原始边使用正数节点编号，对反向边使用负数节点编号进行区分。

算法步骤：

  1. 构建无向邻接表，区分原始边和反向边
  2. 从节点 0 开始 DFS
  3. 遍历过程中统计需要反转的边数
  4. 使用访问标记避免重复遍历

这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，是最优解法。

代码实现

class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<int>> adj(n);
        
        // 构建邻接表，原始边存储为正数，反向边存储为负数
        for (auto& conn : connections) {
            adj[conn[0]].push_back(conn[1]);  // 原始边
            adj[conn[1]].push_back(-conn[0]); // 反向边（用负数标记）
        }
        
        vector<bool> visited(n, false);
        int changes = 0;
        
        function<void(int)> dfs = [&](int node) {
            visited[node] = true;
            for (int neighbor : adj[node]) {
                int next = abs(neighbor);
                if (!visited[next]) {
                    if (neighbor > 0) {  // 原始边，需要反转
                        changes++;
                    }
                    dfs(next);
                }
            }
        };
        
        dfs(0);
        return changes;
    }
};

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        # 构建邻接表
        adj = [[] for _ in range(n)]
        
        for a, b in connections:
            adj[a].append(b)      # 原始边
            adj[b].append(-a)     # 反向边（用负数标记）
        
        visited = [False] * n
        changes = 0
        
        def dfs(node):
            nonlocal changes
            visited[node] = True
            
            for neighbor in adj[node]:
                next_node = abs(neighbor)
                if not visited[next_node]:
                    if neighbor > 0:  # 原始边，需要反转
                        changes += 1
                    dfs(next_node)
        
        dfs(0)
        return changes

public class Solution {
    public int MinReorder(int n, int[][] connections) {
        List<int>[] adj = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }
        
        // 构建邻接表，原始边存储为正数，反向边存储为负数
        foreach (var conn in connections) {
            adj[conn[0]].Add(conn[1]);   // 原始边
            adj[conn[1]].Add(-conn[0]);  // 反向边（用负数标记）
        }
        
        bool[] visited = new bool[n];
        int changes = 0;
        
        void Dfs(int node) {
            visited[node] = true;
            foreach (int neighbor in adj[node]) {
                int next = Math.Abs(neighbor);
                if (!visited[next]) {
                    if (neighbor > 0) {  // 原始边，需要反转
                        changes++;
                    }
                    Dfs(next);
                }
            }
        }
        
        Dfs(0);
        return changes;
    }
}

var minReorder = function(n, connections) {
    // 构建邻接表
    const adj = Array.from({length: n}, () => []);
    
    for (const [a, b] of connections) {
        adj[a].push(b);     // 原始边
        adj[b].push(-a);    // 反向边（用负数标记）
    }
    
    const visited = new Array(n).fill(false);
    let changes = 0;
    
    function dfs(node) {
        visited[node] = true;
        
        for (const neighbor of adj[node]) {
            const next = Math.abs(neighbor);
            if (!visited[next]) {
                if (neighbor > 0) {  // 原始边，需要反转
                    changes++;
                }
                dfs(next);
            }
        }
    }
    
    dfs(0);
    return changes;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要遍历所有 n 个节点和 n-1 条边
空间复杂度O(n) - 邻接表存储空间 + DFS 递归栈空间

相关题目