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] = [ui, vi, cnti] indicates that there is an edge between nodes ui and vi in the original graph, and cnti is the total number of new nodes that you will subdivide the edge into. Note that cnti == 0 means you will not subdivide the edge.
To subdivide the edge [ui, vi], replace it with (cnti + 1) new edges and cnti new nodes. The new nodes are x1, x2, ..., xcnti, and the new edges are [ui, x1], [x1, x2], [x2, x3], ..., [xcnti-1, xcnti], [xcnti, vi].
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.
Example 1:
Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3 Output: 13 Explanation: The edge subdivisions are shown in the image above. The nodes that are reachable are highlighted in yellow.
Example 2:
Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4 Output: 23
Example 3:
Input: edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5 Output: 1 Explanation: Node 0 is disconnected from the rest of the graph, so only node 0 is reachable.
Constraints:
0 <= edges.length <= min(n * (n - 1) / 2, 104)edges[i].length == 30 <= ui < vi < n0 <= cnti <= 1040 <= maxMoves <= 1091 <= n <= 3000Problem Overview: You get an undirected graph where every edge is subdivided into multiple intermediate nodes. Starting from node 0 with maxMoves, count how many original and newly created nodes you can reach without exceeding the move limit.
Approach 1: Dijkstra's Algorithm on Logical Subdivisions (O(E log V) time, O(V + E) space)
Instead of explicitly building all subdivided nodes, treat each edge weight as the number of subdivisions. Run Dijkstra’s algorithm from node 0 using a max heap or priority queue that tracks remaining moves. When you traverse an edge, you consume moves equal to the number of subdivisions plus one to reach the neighbor. Even if you cannot reach the neighbor fully, you can still count partial progress along the subdivided nodes. Maintain how many new nodes were used on each edge from both directions and cap it by the subdivision count.
This approach avoids constructing potentially huge graphs. The algorithm only processes original nodes while logically accounting for intermediate ones. Works well because shortest remaining distance naturally determines how far you can travel along each edge. Uses techniques from shortest path and heap (priority queue) problems.
Approach 2: Depth First Search with Logical Path Expansion (O(E * maxMoves) time, O(V + E) space)
Perform DFS from node 0 while tracking remaining moves. Each recursive step attempts to move along edges and consume subdivisions step by step. If the remaining moves cannot reach the next original node, count only the intermediate nodes along that edge. Maintain a visited structure for edges so subdivided nodes are not double-counted when reached from both sides.
This approach models traversal more directly but becomes inefficient when maxMoves is large. DFS may repeatedly explore similar states. Useful mainly for reasoning about how subdivided nodes contribute to the final count.
Approach 3: Dijkstra on Explicitly Built Subdivided Graph (O((V + S) log (V + S)) time, O(V + S) space)
Construct the full graph where each edge with n subdivisions becomes a chain of n intermediate nodes. After building the expanded graph, run standard Dijkstra from node 0 and count nodes with distance ≤ maxMoves. This makes the logic simple but the graph size becomes huge because the number of new nodes equals the sum of all subdivisions.
This version demonstrates correctness clearly but is impractical for large inputs. It shows why treating subdivisions logically instead of physically is a key optimization when solving graph problems with implicit nodes.
Approach 4: Breadth-First Search with Move Tracking (O(E * maxMoves) time, O(V + E) space)
BFS can simulate movement layer by layer while tracking remaining steps. Each transition consumes part of the move budget along subdivided edges. Similar to DFS, it must track how many intermediate nodes have already been counted from each side of an edge. Because BFS does not prioritize shorter paths like Dijkstra, it may explore inefficient states when the graph has varying subdivision counts.
Recommended for interviews: Dijkstra’s algorithm with logical subdivision tracking. It keeps the graph small, guarantees optimal exploration order, and handles partial edge traversal cleanly. Interviewers expect candidates to recognize that explicitly building the subdivided graph is infeasible and that shortest-path logic solves the move constraint efficiently.
We treat the problem as a shortest path problem. Each edge between nodes in the original graph may be subdivided logically without explicitly constructing all new nodes. We can utilize Dijkstra's algorithm to calculate the shortest paths starting from node 0, considering edge subdivisions.
The function initializes a graph where each node points to a dictionary of its connected nodes treating cnt as weights for route expansion. This is reminiscent of representing weighted edges for pathfinding algorithms. We use a priority queue to maintain node distances akin to Dijkstra's algorithm, continually exploring until all reachable nodes are calculated within maxMoves.
Python
Time Complexity: O(E + V log V), where E is the number of edges and V the number of vertices.
Space Complexity: O(E + V) for storing the graph and distances.
Instead of explicitly constructing the whole subdivided graph, we utilize a DFS strategy. By expanding paths logically through recursion and considering move limits, we can calculate the number of reachable nodes without extra space overhead.
This solution builds an adjacency list to represent the graph. It applies a DFS approach, where each node recursively attempts to visit connected nodes, tracking nodes reached using a set. Subdivisions are not created explicitly, and instead, logical path expansion is calculated by allowable traversal of each edge within given maxMoves.
Python
Time Complexity: O(V + E), where V is the number of vertices and E the number of edges, as it involves visiting nodes and edges logically.
Space Complexity: O(V + E) for adjacency list and visited set.
This approach involves using Dijkstra's algorithm to calculate the shortest distance from node 0 to all other nodes in the subdivided graph. The subdivision requires splitting each edge into a path with additional nodes. The priority queue maintains nodes sorted by distance, ensuring efficient processing of the shortest paths first.
This Python implementation uses a priority queue (heap) to perform a modified Dijkstra's algorithm. The graph is built with adjacency lists where each node's neighbor's distance is stored. As we traverse the graph, we count the nodes within reach (incrementing result res). The 'dist' dictionary keeps the shortest known distance to each node from the starting node, and 'used' tracks how many new nodes we reach in subdivided edges. Finally, we sum up these used nodes for each edge in the given edges list to get the total reachable node count.
Python
JavaScript
C++
Time Complexity: O(E + N log N), where E is the number of edges and N is the number of nodes due to priority queue operations.
Space Complexity: O(N + E), for storing graph, distance, and used nodes mappings.
This approach employs BFS to explore the graph iteratively. Unlike Dijkstra, BFS is less concerned with path cost optimization and focuses on level-wise expansion. It's useful when all edge weights are equal. Here, edges must be handled considering additional costs per neighbor negotiation based on subdivided portions of the graph.
The Java solution explores combinations of reachable nodes using BFS. A queue is used to maintain exploration from the starting node iteratively. Each node's reachable distance is updated if a shorter path via a neighbor is discovered, counting reachable nodes based on the accumulated distance.
Time Complexity: O(E + N^2), due to BFS and operations at each node with the distance array update.
Space Complexity: O(N + E), capturing the adjacency list and additional structures like queue and distance array.
| Approach | Complexity |
|---|---|
| Dijkstra's Algorithm on Logical Subdivisions | Time Complexity: O(E + V log V), where E is the number of edges and V the number of vertices. |
| Depth First Search with Logical Path Expansion | Time Complexity: O(V + E), where V is the number of vertices and E the number of edges, as it involves visiting nodes and edges logically. |
| Dijkstra's Algorithm on Subdivided Graph | Time Complexity: O(E + N log N), where E is the number of edges and N is the number of nodes due to priority queue operations. |
| Alternative Approach - Breadth-First Search (BFS) | Time Complexity: O(E + N^2), due to BFS and operations at each node with the distance array update. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm on Logical Subdivisions | O(E log V) | O(V + E) | Best general solution; handles large subdivision counts efficiently |
| Depth First Search with Logical Path Expansion | O(E * maxMoves) | O(V + E) | Conceptual exploration of reachable nodes when constraints are small |
| Dijkstra on Explicitly Built Subdivided Graph | O((V + S) log (V + S)) | O(V + S) | Educational approach when the subdivided graph size is manageable |
| Breadth-First Search with Move Tracking | O(E * maxMoves) | O(V + E) | Works for small graphs or uniform edge costs |
Reachable Nodes In Subdivided Graph | Leetcode 882 | Live coding session • Coding Decoded • 4,695 views views
Watch 9 more video solutions →Practice Reachable Nodes In Subdivided Graph with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor