题目描述
给你一个 n
个点的 简单有向图 (没有重复边的有向图),节点编号为 0
到 n - 1
。如果这些边是双向边,那么这个图形成一棵 树。
给你一个整数 n
和一个 二维 整数数组 edges
,其中 edges[i] = [u_i, v_i]
表示从节点 u_i
到节点 v_i
有一条 有向边。
边反转 指的是将一条边的方向反转,也就是说一条从节点 u_i
到节点 v_i
的边会变为一条从节点 v_i
到节点 u_i
的边。
对于范围 [0, n - 1]
中的每一个节点 i
,你的任务是分别 独立 计算 最少 需要多少次 边反转,从节点 i
出发经过 一系列有向边,可以到达所有的节点。
请你返回一个长度为 n
的整数数组 answer
,其中 answer[i]
表示从节点 i
出发,可以到达所有节点的 最少边反转 次数。
样例
输入: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。
输入: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 <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= u_i == edges[i][0] < n
0 <= v_i == edges[i][1] < n
u_i != v_i
- 输入保证如果边是双向边,可以得到一棵树。
算法
(深度优先遍历) $O(n)$
- 第一次深度优先遍历,从 $0$ 节点开始,统计出以每个节点 $u$ 为根的子树,需要 边反转 的次数 $f(u)$。
- 第二次深度优先遍历,统计来自父节点方向需要经过 边反转 的次数,并累加答案。设来自父节点方向的反转次数为 $r$。对于从 $(u, v)$ 的一条边,如果 $u \to v$,则递归 $v$ 时,来自 $u$ 方向的反转次数为 $f(u) - f(v) + r + 1$;否则为 $f(u) - f(v) - 1 + r$。
时间复杂度
- 两次深度优先遍历,时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储递归的系统栈,$f$ 数组和答案。
C++ 代码
class Solution {
private:
vector<vector<pair<int, int>>> graph;
vector<int> ans;
vector<int> f;
void dfs(int u, int fa) {
for (const auto &e : graph[u]) {
if (e.first == fa)
continue;
dfs(e.first, u);
f[u] += f[e.first] + e.second;
}
}
void dfs2(int u, int fa, int r) {
ans[u] = f[u] + r;
for (const auto &e : graph[u]) {
if (e.first == fa)
continue;
if (e.second == 0)
dfs2(e.first, u, f[u] - f[e.first] + r + 1);
else
dfs2(e.first, u, f[u] - f[e.first] + r - 1);
}
}
public:
vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
graph.resize(n);
for (const auto &e : edges) {
graph[e[0]].emplace_back(e[1], 0);
graph[e[1]].emplace_back(e[0], 1);
}
f.resize(n, 0);
dfs(0, -1);
ans.resize(n);
dfs2(0, -1, 0);
return ans;
}
};