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

Reachable Nodes In Subdivided Graph

Number: 918

Difficulty: Hard

Paid? No

Companies: PhonePe

Problem Description

Given an undirected graph where each edge [u, v, cnt] is subdivided into (cnt + 1) segments by inserting cnt new nodes along the edge, determine how many nodes in the resulting graph are reachable from node 0 using at most maxMoves moves. A move traverses one edge in the subdivided graph.

Key Insights

  • Instead of explicitly constructing the subdivided graph (which could be huge), use a modified graph algorithm on the original graph.
  • Use Dijkstra’s algorithm to compute the minimum number of moves required to reach each original node from node 0.
  • For each edge, determine how many of the subdivided nodes can be reached from either end based on the remaining moves.
  • For each edge between u and v with cnt subdivided nodes, the count of reachable new nodes is min(cnt, max(0, maxMoves - dist[u]) + max(0, maxMoves - dist[v])).

Space and Time Complexity

Time Complexity: O(E log N) where E is the number of edges and N is the number of original nodes. Space Complexity: O(N + E) for storing the graph and distance array.

Solution

We solve the problem by using Dijkstra’s algorithm on the original graph where the weight to traverse an edge [u, v, cnt] is (cnt + 1). This yields the minimum moves required to reach each original node. Once we have these distances:

  1. Count each original node for which the distance is within maxMoves.
  2. For every subdivided edge, compute the available moves remaining from both endpoints.
  3. The number of reachable subdivided nodes on an edge is the minimum between cnt and the sum of moves remaining from both endpoints. By summing these counts, we obtain the total number of reachable nodes in the subdivided graph.

Code Solutions

import heapq

class Solution:
    def reachableNodes(self, edges, maxMoves, n):
        # Build the graph where each entry is (neighbor, subdivision count)
        graph = [[] for _ in range(n)]
        for u, v, cnt in edges:
            graph[u].append((v, cnt))
            graph[v].append((u, cnt))
        
        # Initialize distance array where each node's distance is set to infinity except the source (node 0)
        dist = {i: float('inf') for i in range(n)}
        dist[0] = 0

        # Use a min-heap (priority queue) for Dijkstra's algorithm
        heap = [(0, 0)]  # Each entry: (current distance, node)
        
        while heap:
            d, node = heapq.heappop(heap)
            if d > dist[node]:
                continue
            # Explore neighbors and update distances if a shorter path is found
            for neighbor, cnt in graph[node]:
                newDist = d + cnt + 1
                if newDist < dist[neighbor]:
                    dist[neighbor] = newDist
                    heapq.heappush(heap, (newDist, neighbor))
        
        result = 0
        # Count original nodes that are directly reachable within maxMoves
        for d in dist.values():
            if d <= maxMoves:
                result += 1
        
        # Count the reachable subdivided nodes on each edge
        for u, v, cnt in edges:
            # Calculate remaining moves from each endpoint
            movesFromU = max(0, maxMoves - dist[u])
            movesFromV = max(0, maxMoves - dist[v])
            # The reachable subdivided nodes is the minimum of total subdivisions and moves available from both sides
            result += min(cnt, movesFromU + movesFromV)
        return result
← Back to All Questions