Skip to content

Practice Minimum Edge Reversals So Every Node Is Reachable

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#2858
LeetCode Problem

Minimum Edge Reversals So Every Node Is Reachable

Problem Statement

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.

Source: Minimum Edge Reversals So Every Node Is Reachable on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
n = 4, edges = [[2,0],[2,1],[1,3]]
Output
[1,1,0,2]

# Example 2

Input
n = 3, edges = [[1,2],[2,0]]
Output
[2,0,1]

Constraints

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
The input is generated such that if the edges were bi-directional, the graph would be a tree.

Related LeetCode Problems

Practice more problems similar to Minimum Edge Reversals So Every Node Is Reachable.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.