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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reachable Nodes In Subdivided Graph

Difficulty: Hard

Problem Description

You are given an undirected graph (the "original graph") with n nodes labeled from 0 to n - 1. You decide to subdivide each edge in the graph into a chain of nodes, with the number of new nodes varying between each edge. The graph is given as a 2D array of edges where edges[i] = [u_i, v_i, cnt_i] indicates that there is an edge between nodes u_i and v_i in the original graph, and cnt_i is the total number of new nodes that you will subdivide the edge into. To subdivide the edge [u_i, v_i], replace it with (cnt_i + 1) new edges and cnt_i new nodes. In this new graph, you want to know how many nodes are reachable from the node 0, where a node is reachable if the distance is maxMoves or less. Given the original graph and maxMoves, return the number of nodes that are reachable from node 0 in the new graph.

Key Insights

  • The graph can be transformed by subdividing edges into new nodes, increasing the overall number of reachable nodes.
  • The distance from the starting node (node 0) to any other node needs to be calculated while considering the subdivisions.
  • A priority queue (min-heap) can be used to efficiently find the nodes that can be reached within maxMoves.

Space and Time Complexity

Time Complexity: O(E log E) where E is the number of edges, due to the use of a priority queue to explore the graph. Space Complexity: O(N + E) where N is the number of nodes and E is the number of edges, to store the graph representation and the priority queue.

Solution

To solve this problem, we can utilize Dijkstra's algorithm with a priority queue to keep track of the minimum moves needed to reach each node. First, we will create an adjacency list representation of the graph, considering the subdivisions of edges into new nodes. As we explore the graph starting from node 0, we will track the total number of reachable nodes within the given maxMoves.

  1. Build the graph with subdivided edges.
  2. Use a priority queue to process nodes starting from node 0.
  3. For each node, check its neighbors and update the reachable distance.
  4. Count all nodes that can be reached within maxMoves.

Code Solutions

import heapq
from collections import defaultdict

def reachableNodes(edges, maxMoves, n):
    graph = defaultdict(list)
    
    # Build the graph with subdivisions
    for u, v, cnt in edges:
        graph[u].append((v, cnt))
        graph[v].append((u, cnt))
    
    # Priority queue to perform Dijkstra's algorithm
    pq = [(0, 0)]  # (moves, node)
    visited = {}
    reachable = 0
    
    while pq:
        moves, node = heapq.heappop(pq)
        
        if node in visited:
            continue
        
        visited[node] = moves
        reachable += 1
        
        for neighbor, cnt in graph[node]:
            if neighbor in visited:
                continue
            
            # Calculate the total moves to reach the neighbor through subdivisions
            total_moves = moves + cnt + 1
            
            if total_moves <= maxMoves:
                heapq.heappush(pq, (total_moves, neighbor))
    
    return reachable
← Back to All Questions