调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你一个 n 个点的 简单有向图 (没有重复边的有向图),节点编号为 0 到 n - 1 。如果这些边是双向边,那么这个图形成一棵  。

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

边反转 指的是将一条边的方向反转,也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。

对于范围 [0, n - 1] 中的每一个节点 i ,你的任务是分别 独立 计算 最少 需要多少次 边反转 ,从节点 i 出发经过 一系列有向边 ,可以到达所有的节点。

请你返回一个长度为 n 的整数数组 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 :不需要反转就可以从节点 2 出发到达所有节点。
所以 answer[1] = 0 。
对于节点 2 :反转 [1,2] ,从节点 2 出发可以到达所有节点。
所以 answer[2] = 1 。

 

提示:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ui == edges[i][0] < n
  • 0 <= vi == edges[i][1] < n
  • ui != vi
  • 输入保证如果边是双向边,可以得到一棵树。
通过次数
2.5K
提交次数
3.8K
通过率
67.0%


相关企业

提示 1
The problem can be solved using tree DP.

提示 2
Using node 0 as the root, let dp[x] be the minimum number of edge reversals so node x can reach every node in its subtree.

提示 3
Using a DFS traversing the edges bidirectionally, we can compute dp.
dp[x] = dp[y] + (1 if the edge between x and y is going from y to x; 0 otherwise), where x is the parent of y.

提示 4
Let answer[x] be the minimum number of edge reversals so it is possible to reach any other node starting from node x.

提示 5
Using another DFS starting from node 0 and traversing the edges bidirectionally, we can compute answer.
answer[0] = dp[0]
answer[y] = answer[x] + (1 if the edge between x and y is going from x to y; -1 otherwise), where x is the parent of y.

相似题目

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
n =
4
edges =
[[2,0],[2,1],[1,3]]
Source