We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Edge Reversals So Every Node Is Reachable

Number: 3105

Difficulty: Hard

Paid? No

Companies: MathWorks, Meesho

Problem Description

Given a directed tree (i.e. if the edges were treated as undirected, they would form a tree) with n nodes (labeled 0 to n-1) and n-1 directed edges, we want to compute for every node i the minimum number of edge reversals required so that starting from node i it is possible to reach every other node following a sequence of directed edges.

Key Insights

  • The underlying undirected structure is a tree.
  • For each directed edge from u to v, if we travel from u to v, no reversal is needed; if we traverse in the opposite direction (v to u), we must “reverse” this edge (cost = 1).
  • We can transform the problem into one on an undirected tree by assigning a cost (0 or 1) to each “direction” on every edge.
  • First compute the total reversal cost for an arbitrary root (for example, node 0) with a DFS.
  • Then use a re-rooting (tree DP) technique to compute the answer for every node in O(n) time.
  • The re-rooting relation: when moving the root from node u to its neighbor v, update the cost as
    • ans[v] = ans[u] + (if the edge from u to v was originally directed u->v then add 1, else subtract 1).

Space and Time Complexity

Time Complexity: O(n), since we process all nodes and edges using DFS twice (once for initial DFS and once for re-rooting). Space Complexity: O(n), for storing the tree (adjacency list) and recursion stack in the worst-case.

Solution

We will first build an undirected graph from the given edge list where each edge is stored twice:

  • For an edge u->v, add (v, 0) to u’s list (indicating correct travel direction) and add (u, 1) to v’s list (indicating reversal if traveling from v to u). Next, perform a DFS from an arbitrary root (node 0) to compute the reversal cost needed when the root is 0. Then, use another re-root DFS: for an edge between u and v, if the original directed edge was from u to v (weight 0) then switching the root from u to v means that edge becomes “against” the new root’s requirement so we add 1; if the edge was originally v->u (weight 1), then switching reduces the cost by 1. This method calculates the answer for every node.

Code Solutions

# Python solution for Minimum Edge Reversals So Every Node Is Reachable

import sys
sys.setrecursionlimit(200000)

def minEdgeReversals(n, edges):
    # Build graph with (neighbor, cost) pairs.
    # cost = 0 means edge u->v exists; cost = 1 means reversal needed.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append((v, 0))  # original edge u->v: no reversal if traversed from u to v
        graph[v].append((u, 1))  # if we go from v to u later, we need to reverse
    
    # ans[i] will hold total cost when node i is chosen as the root.
    ans = [0] * n
    visited = [False] * n

    # First DFS: Compute cost for root 0.
    def dfs_cost(node):
        visited[node] = True
        for neighbor, cost in graph[node]:
            if not visited[neighbor]:
                ans[0] += cost  # cost from node->neighbor
                dfs_cost(neighbor)
    
    dfs_cost(0)
    
    # Second DFS: Re-rooting step.
    visited = [False] * n
    def dfs_reroot(node):
        visited[node] = True
        for neighbor, cost in graph[node]:
            if not visited[neighbor]:
                # If the edge from node -> neighbor originally had cost 0,
                # then while re-rooting, this edge will become reversed (thus add cost 1).
                # Otherwise, if cost==1, that edge is "fixed" now (thus subtract 1).
                ans[neighbor] = ans[node] + (1 if cost == 0 else -1)
                dfs_reroot(neighbor)
    
    dfs_reroot(0)
    return ans

# Example usage:
n = 4
edges = [[2,0],[2,1],[1,3]]
print(minEdgeReversals(n, edges))  # Output should be [1,1,0,2]
← Back to All Questions