2858. Minimum Edge Reversals So Every Node Is Reachable LeetCode Solution
In this guide, you will get 2858. Minimum Edge Reversals So Every Node Is Reachable LeetCode Solution with the best time and space complexity. The solution to Minimum Edge Reversals So Every Node Is Reachable problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Edge Reversals So Every Node Is Reachable
There is a simple directed graph with n nodes labeled from 0 to n – 1. The graph would form a tree if its edges were bi-directional.
You are given an integer n and a 2D integer array edges, where edges[i] = [ui, vi] represents a directed edge going from node ui to node vi.
An edge reversal changes the direction of an edge, i.e., a directed edge going from node ui to node vi becomes a directed edge going from node vi to node ui.
For every node i in the range [0, n – 1], your task is to independently calculate the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.
Return an integer array answer, where answer[i] is the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.
Input: n = 4, edges = [[2,0],[2,1],[1,3]]
Output: [1,1,0,2]
Explanation: The image above shows the graph formed by the edges.
For node 0: after reversing the edge [2,0], it is possible to reach any other node starting from node 0.
So, answer[0] = 1.
For node 1: after reversing the edge [2,1], it is possible to reach any other node starting from node 1.
So, answer[1] = 1.
For node 2: it is already possible to reach any other node starting from node 2.
So, answer[2] = 0.
For node 3: after reversing the edges [1,3] and [2,1], it is possible to reach any other node starting from node 3.
So, answer[3] = 2.
Example 2:
Input: n = 3, edges = [[1,2],[2,0]]
Output: [2,0,1]
Explanation: The image above shows the graph formed by the edges.
For node 0: after reversing the edges [2,0] and [1,2], it is possible to reach any other node starting from node 0.
So, answer[0] = 2.
For node 1: it is already possible to reach any other node starting from node 1.
So, answer[1] = 0.
For node 2: after reversing the edge [1, 2], it is possible to reach any other node starting from node 2.
So, answer[2] = 1.
Constraints:
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
The input is generated such that if the edges were bi-directional, the graph would be a tree.
Complexity Analysis
Time Complexity: O(|V| + |E|)
Space Complexity: O(|V| + |E|)
2858. Minimum Edge Reversals So Every Node Is Reachable LeetCode Solution in C++
class Solution {
public:
vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
vector<int> ans(n);
vector<vector<pair<int, bool>>> graph(n);
vector<bool> seen(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
graph[u].emplace_back(v, /*isForward=*/true);
graph[v].emplace_back(u, /*isForward=*/false);
}
vector<int> mem(n, -1);
ans[0] = minEdgeReversals(graph, 0, seen, mem);
seen = vector<bool>(n);
dfs(graph, 0, seen, ans);
return ans;
}
private:
// Returns the minimum number of edge reversals so node u can reach every
// node in its subtree.
int minEdgeReversals(const vector<vector<pair<int, bool>>>& graph, int u,
vector<bool>& seen, vector<int>& mem) {
if (mem[u] != -1)
return mem[u];
int res = 0;
seen[u] = true;
for (const auto& [v, isForward] : graph[u]) {
if (seen[v])
continue;
seen[v] = true;
res += minEdgeReversals(graph, v, seen, mem) + (isForward ? 0 : 1);
}
return mem[u] = res;
}
void dfs(const vector<vector<pair<int, bool>>>& graph, int u,
vector<bool>& seen, vector<int>& ans) {
seen[u] = true;
for (const auto& [v, isForward] : graph[u]) {
if (seen[v])
continue;
seen[v] = true;
ans[v] = ans[u] + (isForward ? 1 : -1);
dfs(graph, v, seen, ans);
}
}
}; /* code provided by PROGIEZ */
2858. Minimum Edge Reversals So Every Node Is Reachable LeetCode Solution in Java
class Solution {
public int[] minEdgeReversals(int n, int[][] edges) {
int[] ans = new int[n];
List<Pair<Integer, Boolean>>[] graph = new List[n];
boolean[] seen = new boolean[n];
for (int i = 0; i < n; i++)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(new Pair<>(v, /*isForward=*/true));
graph[v].add(new Pair<>(u, /*isForward=*/false));
}
Integer[] mem = new Integer[n];
ans[0] = minEdgeReversals(graph, 0, seen, mem);
seen = new boolean[n];
dfs(graph, 0, seen, ans);
return ans;
}
// Returns the minimum number of edge reversals so node u can reach every
// node in its subtree.
private int minEdgeReversals(List<Pair<Integer, Boolean>>[] graph, int u, boolean[] seen,
Integer[] mem) {
if (mem[u] != null)
return mem[u];
int res = 0;
seen[u] = true;
for (Pair<Integer, Boolean> pair : graph[u]) {
final int v = pair.getKey();
final boolean isForward = pair.getValue();
if (seen[v])
continue;
seen[v] = true;
res += minEdgeReversals(graph, v, seen, mem) + (isForward ? 0 : 1);
}
return mem[u] = res;
}
private void dfs(List<Pair<Integer, Boolean>>[] graph, int u, boolean[] seen, int[] ans) {
seen[u] = true;
for (Pair<Integer, Boolean> pair : graph[u]) {
final int v = pair.getKey();
final boolean isForward = pair.getValue();
if (seen[v])
continue;
seen[v] = true;
ans[v] = ans[u] + (isForward ? 1 : -1);
dfs(graph, v, seen, ans);
}
}
} // code provided by PROGIEZ
2858. Minimum Edge Reversals So Every Node Is Reachable LeetCode Solution in Python
class Solution:
def minEdgeReversals(self, n: int, edges: list[list[int]]) -> list[int]:
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append((v, True)) # 1 means (u -> v)
graph[v].append((u, False)) # 0 means (v <- u)
seen = {0}
@functools.lru_cache(None)
def dp(u: int) -> int:
"""
Returns the minimum number of edge reversals so node u can reach every
node in its subtree.
"""
res = 0
for v, isForward in graph[u]:
if v in seen:
continue
seen.add(v)
res += dp(v) + (0 if isForward else 1)
return res
ans = [0] * n
ans[0] = dp(0)
def dfs(u: int) -> None:
for v, isForward in graph[u]:
if v in seen:
continue
seen.add(v)
ans[v] = ans[u] + (1 if isForward else -1)
dfs(v)
seen = {0}
dfs(0)
return ans # code by PROGIEZ
