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 <= 3000We 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.
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.
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.
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.
C#
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. |
Reachable Nodes In Subdivided Graph | Leetcode 882 | Live coding session • Coding Decoded • 4,077 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