#2858

Minimum Edge Reversals So Every Node Is Reachable

expert · 1240 · lc hard +32 · verified · 57.4% accepted · 415 likes · top 53%

Description

A simple directed graph on n nodes (labeled 0 to n - 1) forms a tree when its edges are treated as undirected. A 2D array edges gives directed edges: edges[i] = [ui, vi] means an edge from ui to vi.

Reversing an edge flips its direction.

For every node i in [0, n - 1], independently find the minimum reversals needed so that every other node is reachable from i.

Return an array answer where answer[i] is that minimum for node i.

Example 1:

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.

Code

1

2

3

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]: