Minimum Edge Reversals So Every Node Is Reachable — LeetCode 2858 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        ans = [0] * n
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append((y, 1))
            g[y].append((x, -1))

        def dfs(i: int, fa: int):
            for j, k in g[i]:
                if j != fa:
                    ans[0] += int(k < 0)
                    dfs(j, i)

        dfs(0, -1)

        def dfs2(i: int, fa: int):
            for j, k in g[i]:
                if j != fa:
                    ans[j] = ans[i] + k
                    dfs2(j, i)

        dfs2(0, -1)
        return ans

Complexity

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 2858. Minimum Edge Reversals So Every Node Is Reachable is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Related problems