Hard

题目描述

有一个简单的有向图，包含 n 个节点，标号从 0 到 n - 1。如果图的边都是双向的，它将形成一棵树。

给你一个整数 n 和一个二维整数数组 edges，其中 edges[i] = [ui, vi] 表示一条从节点 ui 到节点 vi 的有向边。

边反转会改变边的方向，即从节点 ui 到节点 vi 的有向边变成从节点 vi 到节点 ui 的有向边。

对于范围 [0, n - 1] 内的每个节点 i，你的任务是独立计算使得从节点 i 出发通过一系列有向边能够到达任何其他节点所需的最少边反转次数。

返回一个整数数组 answer，其中 answer[i] 是使得从节点 i 出发通过一系列有向边能够到达任何其他节点所需的最少边反转次数。

示例 1：

输入：n = 4, edges = [[2,0],[2,1],[1,3]]
输出：[1,1,0,2]
解释：
对于节点 0：反转边 [2,0] 后，可以从节点 0 到达任何其他节点。
所以，answer[0] = 1。
对于节点 1：反转边 [2,1] 后，可以从节点 1 到达任何其他节点。
所以，answer[1] = 1。
对于节点 2：已经可以从节点 2 到达任何其他节点。
所以，answer[2] = 0。
对于节点 3：反转边 [1,3] 和 [2,1] 后，可以从节点 3 到达任何其他节点。
所以，answer[3] = 2。

示例 2：

输入：n = 3, edges = [[1,2],[2,0]]
输出：[2,0,1]
解释：
对于节点 0：反转边 [2,0] 和 [1,2] 后，可以从节点 0 到达任何其他节点。
所以，answer[0] = 2。
对于节点 1：已经可以从节点 1 到达任何其他节点。
所以，answer[1] = 0。
对于节点 2：反转边 [1,2] 后，可以从节点 2 到达任何其他节点。
所以，answer[2] = 1。

提示：

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ui == edges[i][0] < n
  • 0 <= vi == edges[i][1] < n
  • ui != vi
  • 输入保证如果边是双向的，图将形成一棵树。

解题思路

这是一个经典的换根DP问题。核心思想是利用树形DP的思想，分两个阶段计算答案。

第一阶段：以节点0为根的树形DP 首先将有向图转换为无向图（双向边），以节点0为根进行DFS。对于每个节点x，计算dp[x]表示从x出发能够到达其子树内所有节点所需的最少边反转次数。

状态转移方程为：dp[x] = Σ(dp[y] + cost(x→y))，其中y是x的子节点，cost(x→y)表示如果原图中边的方向是从y到x则需要反转（代价为1），否则代价为0。

第二阶段：换根DP计算最终答案 通过第一阶段，我们得到了以节点0为根时的答案answer[0] = dp[0]。现在需要计算其他节点作为根时的答案。

当我们从节点x转移到其子节点y时：

  • 如果原图中边的方向是x→y，那么answer[y] = answer[x] + 1（需要多反转一条边）
  • 如果原图中边的方向是y→x，那么answer[y] = answer[x] - 1（少需要反转一条边）

这样通过一次DFS遍历，就能得到所有节点的答案。

时间复杂度O(n)，空间复杂度O(n)，是最优解法。

代码实现

class Solution {
public:
    vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> graph(n);
        
        // 构建双向图，标记原始边的方向
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            graph[u].push_back({v, 0}); // 正向边，不需要反转
            graph[v].push_back({u, 1}); // 反向边，需要反转
        }
        
        vector<int> dp(n, 0);
        vector<bool> visited(n, false);
        
        // 第一次DFS：计算以0为根时每个节点的子树代价
        function<void(int)> dfs1 = [&](int u) {
            visited[u] = true;
            for (auto [v, cost] : graph[u]) {
                if (!visited[v]) {
                    dfs1(v);
                    dp[u] += dp[v] + cost;
                }
            }
        };
        
        dfs1(0);
        
        vector<int> answer(n, 0);
        answer[0] = dp[0];
        
        // 第二次DFS：换根DP计算所有节点的答案
        function<void(int)> dfs2 = [&](int u) {
            visited[u] = true;
            for (auto [v, cost] : graph[u]) {
                if (!visited[v]) {
                    // 从u转移到v时，边的方向变化
                    answer[v] = answer[u] + (cost == 0 ? 1 : -1);
                    dfs2(v);
                }
            }
        };
        
        fill(visited.begin(), visited.end(), false);
        dfs2(0);
        
        return answer;
    }
};

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        from collections import defaultdict
        
        graph = defaultdict(list)
        
        # 构建双向图，标记原始边的方向
        for u, v in edges:
            graph[u].append((v, 0))  # 正向边，不需要反转
            graph[v].append((u, 1))  # 反向边，需要反转
        
        dp = [0] * n
        visited = [False] * n
        
        # 第一次DFS：计算以0为根时每个节点的子树代价
        def dfs1(u):
            visited[u] = True
            for v, cost in graph[u]:
                if not visited[v]:
                    dfs1(v)
                    dp[u] += dp[v] + cost
        
        dfs1(0)
        
        answer = [0] * n
        answer[0] = dp[0]
        
        # 第二次DFS：换根DP计算所有节点的答案
        def dfs2(u):
            visited[u] = True
            for v, cost in graph[u]:
                if not visited[v]:
                    # 从u转移到v时，边的方向变化
                    answer[v] = answer[u] + (1 if cost == 0 else -1)
                    dfs2(v)
        
        visited = [False] * n
        dfs2(0)
        
        return answer

public class Solution {
    public int[] MinEdgeReversals(int n, int[][] edges) {
        var graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        // 构建双向图，标记原始边的方向
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1];
            graph[u].Add((v, 0)); // 正向边，不需要反转
            graph[v].Add((u, 1)); // 反向边，需要反转
        }
        
        var dp = new int[n];
        var visited = new bool[n];
        
        // 第一次DFS：计算以0为根时每个节点的子树代价
        void Dfs1(int u) {
            visited[u] = true;
            foreach (var (v, cost) in graph[u]) {
                if (!visited[v]) {
                    Dfs1(v);
                    dp[u] += dp[v] + cost;
                }
            }
        }
        
        Dfs1(0);
        
        var answer = new int[n];
        answer[0] = dp[0];
        
        // 第二次DFS：换根DP计算所有节点的答案
        void Dfs2(int u) {
            visited[u] = true;
            foreach (var (v, cost) in graph[u]) {
                if (!visited[v]) {
                    // 从u转移到v时，边的方向变化
                    answer[v] = answer[u] + (cost == 0 ? 1 : -1);
                    Dfs2(v);
                }
            }
        }
        
        Array.Fill(visited, false);
        Dfs2(0);
        
        return answer;
    }
}

var minEdgeReversals = function(n, edges) {
    const graph = Array.from({length: n}, () => []);
    
    // Build bidirectional graph with edge costs
    // cost 0 for original direction, cost 1 for reverse direction
    for (const [u, v] of edges) {
        graph[u].push([v, 0]); // original direction, no cost
        graph[v].push([u, 1]); // reverse direction, cost 1
    }
    
    const answer = new Array(n);
    
    // DFS to calculate minimum reversals from a starting node
    function dfs(start) {
        const visited = new Array(n).fill(false);
        let totalCost = 0;
        
        function traverse(node) {
            visited[node] = true;
            for (const [neighbor, cost] of graph[node]) {
                if (!visited[neighbor]) {
                    totalCost += cost;
                    traverse(neighbor);
                }
            }
        }
        
        traverse(start);
        return totalCost;
    }
    
    // Calculate answer for each starting node
    for (let i = 0; i < n; i++) {
        answer[i] = dfs(i);
    }
    
    return answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)
空间复杂度O(n)
  • 时间复杂度：需要进行两次DFS遍历，每次遍历访问所有节点和边各一次，总时间复杂度为O(n)
  • 空间复杂度：需要存储图的邻接表、DP数组、访问标记数组等，空间复杂度为O(n)

相关题目