882. Reachable Nodes In Subdivided Graph
Problem Description
In this problem, we are given an undirected graph, represented by a list of its edges. The nodes in this graph are numbered from 0 to n - 1. Each edge connects two nodes and may be subdivided into smaller sub-edges by adding additional nodes along the edge. The array edges
contains elements [u_i, v_i, cnt_i]
which describe an edge between nodes u_i
and v_i
, and cnt_i
is the number of new nodes to be inserted on this edge, thereby breaking the original edge into cnt_i + 1
smaller edges.
After subdividing edges in this manner, we want to determine the number of nodes that are reachable from node 0, using at most maxMoves
moves. A move consists of traversing from one node to an adjacent one via an edge. Reachable nodes include all nodes that can be reached from node 0 with a number of steps equal to or less than maxMoves
.
Intuition
The core idea behind the solution is to first calculate the minimum number of moves needed to reach each node from node 0 by utilizing a priority queue (min heap) to perform Dijkstra's algorithm. We initialize a distance array dist
that keeps track of the minimum distance to every node from node 0, with the distance to node 0 being 0 and the rest being infinity.
During the execution of Dijkstra's algorithm, we keep extracting the node with the smallest distance from the queue, and for each neighbor of this node, we calculate if the distance to this neighbor can be improved by taking the path through the current node. If so, we update the distance to the neighbor and place it into the queue with the new calculated distance.
After determining the minimum distances, the next step is to count the nodes reachable from node 0 with maxMoves
moves. For every node with a distance less than or equal to maxMoves
, it is directly reachable, so we increment our reachable node count.
Moreover, for every subdivided edge, we may potentially reach additional new nodes created in the subdivision. To find out precisely how many of these subdivision nodes we can reach, we look at both ends of the original edge. For each end, we find out how many moves we have left to traverse the subdivided edge after reaching this end, taking the smaller of the cnt
and the remaining moves as the count of additional reachable nodes from that end. The minimum of cnt
or the sum of additional nodes reachable from both ends will be the number of new nodes reachable on the edge.
Finally, we sum up the number of directly reachable nodes and additional reachable nodes on subdivided edges to get our answer.
Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.
Solution Approach
The implementation of the problem follows the intuition we described earlier. The details are as follows:
-
Graph Representation: We construct a graph using a defaultdict of lists called
g
to hold our adjacency list. Each node in the graph has a list of tuples representing its neighbors and the number of new edges created when subdividing the edge connecting it with the neighbor. -
Priority Queue with Dijkstra's Algorithm: We use a min-heap priority queue to determine the shortest path from node 0 to all other nodes in the graph. The queue is initialized with a tuple
(0, 0)
representing a distance of 0 to reach node 0. -
Updating Distances: A list
dist
keeps track of the shortest distance from node 0 to every other node, with an initial distance of 0 for node 0 and infinity for all other nodes. We use a while loop to repeatedly pop the node with the smallest distance from the priority queue, and for each of its neighbors, we calculate if there is a shorter path to this neighbor through the current node (updating thedist
list and the queue accordingly). -
Counting Reachable Nodes:
- Directly Reachable Nodes: For each node, if its distance from node 0 is less than or equal to
maxMoves
, it is counted as reachable. - New Nodes on Subdivided Edges: For each edge, we determine how many new nodes can be reached by calculating the number of steps we can take on the subdivided edge from both ends. This is done by taking the smaller of the
cnt
(total new nodes on the edge) and themaxMoves
minus the distance to each end of the edge.
- Directly Reachable Nodes: For each node, if its distance from node 0 is less than or equal to
-
Calculating the Answer: The variable
ans
keeps track of the count of directly reachable nodes and the total count of new nodes reachable on all subdivided edges. For eachu, v, cnt
in theedges
list, we calculate the sum of reachable new nodes from bothu
andv
, and add the smaller of thecnt
and this sum toans
. Finally,ans
is returned as the final count of reachable nodes from node 0.
In terms of algorithms and patterns, this solution employs:
- Dijkstra's Algorithm: For finding the shortest path in a weighted graph.
- Priority Queue (Min-Heap): For efficiently finding and updating the closest unvisited node.
- Greedy Approach: When calculating how many new nodes can be reached on a subdivided edge, we always take as many steps as possible from one end before considering the steps that can be taken from the other end.
- Adjacency List Representation of a Graph: To manage the graph structure efficiently.
The combination of these methods efficiently solves the problem by first finding the shortest paths using Dijkstra's algorithm and then iteratively counting the reachable nodes from node 0 within maxMoves
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach described above. Suppose we have the following inputs:
n = 4
(nodes are numbered from 0 to 3)edges = [[0, 1, 2], [0, 2, 1], [1, 3, 1]]
maxMoves = 2
The graph looks like this initially:
10 --1-- 1 2| | 32 3
After adding the subdivided nodes, our graph looks like this:
10 --0--new0--0-- 1 2| | 32 new1 3
To solve this problem, we follow the steps described:
Graph Representation: We create an adjacency list:
1g = { 2 0: [(1, 2), (2, 1)], 3 1: [(0, 2), (3, 1)], 4 2: [(0, 1)], 5 3: [(1, 1)] 6}
Priority Queue with Dijkstra's Algorithm:
We use a priority queue to store distances from node 0. We initialize it with (0,0)
(distance 0 to reach node 0).
Updating Distances:
We keep updating the dist
array until the priority queue is empty. Initially dist = [0, inf, inf, inf]
. After processing, dist
might look like [0, 2, 1, 3]
.
Counting Reachable Nodes:
- Directly Reachable Nodes: Nodes 1 and 2 are directly reachable since their distances are
2
and1
, respectively, which are less than or equal tomaxMoves
(2). - New Nodes on Subdivided Edges:
- From edge
0-1
, with 2 new nodes (new0 and new1), starting from node 0, we can reach new0 since it's 1 move away (maxMoves - dist[0] = 2 - 0 = 2). But we cannot move further as we've reached maxMoves. - From edge
1-3
, with 1 new node, starting from node 1, we can't reach the new node sincemaxMoves - dist[1] = 2 - 2 = 0
moves left, so no new nodes can be visited from that edge on the side of node 1.
- From edge
Calculating the Answer:
- Directly reachable nodes: 2
- Reachable new nodes on edge
0-1
: 1 - Reachable new nodes on edge
1-3
: 0 - Total reachable nodes including node 0: 1 (node 0 itself) + 2 (directly reachable nodes) + 1 (reachable new nods on edge
0-1
) = 4.
Therefore, the total number of nodes that are reachable from node 0 using at most maxMoves
moves is 4.
Solution Implementation
1from heapq import heappop, heappush
2from collections import defaultdict
3
4class Solution:
5 def reachable_nodes(self, edges, max_moves, n):
6 # Create a graph where each node contains a list of tuples (neighbor, count+1)
7 graph = defaultdict(list)
8 for u, v, count_nodes in edges:
9 graph[u].append((v, count_nodes + 1))
10 graph[v].append((u, count_nodes + 1))
11
12 # Priority queue for Dijkstra's algorithm;
13 # contains pairs (distance_from_start, node)
14 queue = [(0, 0)]
15
16 # Distance array, initialized with infinity except for start node
17 distances = [0] + [float('inf')] * (n - 1)
18
19 # Dijkstra's algorithm to find the shortest paths from node 0 to all other nodes
20 while queue:
21 distance, current_node = heappop(queue)
22 for neighbor, weight in graph[current_node]:
23 new_distance = distance + weight
24 if new_distance < distances[neighbor]:
25 distances[neighbor] = new_distance
26 heappush(queue, (new_distance, neighbor))
27
28 # Calculate how many nodes are reachable within max_moves
29 answer = sum(distance <= max_moves for distance in distances)
30
31 # Calculate how many new nodes are reachable via the leftover moves after reaching node u or v
32 for u, v, count_nodes_between in edges:
33 leftover_moves_u = max(0, max_moves - distances[u])
34 leftover_moves_v = max(0, max_moves - distances[v])
35 reachable_through_u = min(count_nodes_between, leftover_moves_u)
36 reachable_through_v = min(count_nodes_between, leftover_moves_v)
37 additional_nodes = min(count_nodes_between, reachable_through_u + reachable_through_v)
38 answer += additional_nodes
39
40 return answer
41
1class Solution {
2 public int reachableNodes(int[][] edges, int maxMoves, int n) {
3 // Create an adjacency list to represent the graph
4 List<int[]>[] graph = new List[n];
5 Arrays.setAll(graph, element -> new ArrayList<>());
6 for (int[] edge : edges) {
7 int from = edge[0], to = edge[1], cost = edge[2] + 1;
8 graph[from].add(new int[] {to, cost});
9 graph[to].add(new int[] {from, cost});
10 }
11
12 // Initialize distances array with a high value
13 int[] distances = new int[n];
14 Arrays.fill(distances, Integer.MAX_VALUE);
15 // Priority queue for Dijkstra's algorithm, sorting by distance
16 PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
17 priorityQueue.offer(new int[] {0, 0}); // distance, node
18 distances[0] = 0; // Distance to starting node is 0
19
20 // Dijkstra's algorithm to find shortest distances to all other nodes
21 while (!priorityQueue.isEmpty()) {
22 int[] polled = priorityQueue.poll();
23 int distance = polled[0], current = polled[1];
24 for (int[] next : graph[current]) {
25 int neighbor = next[0], edgeCost = next[1];
26 if (distance + edgeCost < distances[neighbor]) {
27 distances[neighbor] = distance + edgeCost;
28 priorityQueue.offer(new int[] {distances[neighbor], neighbor});
29 }
30 }
31 }
32
33 // Count all nodes reachable within max moves
34 int reachableNodesCount = 0;
35 for (int dist : distances) {
36 if (dist <= maxMoves) {
37 ++reachableNodesCount;
38 }
39 }
40
41 // Calculate the number of new nodes reached through edges partially
42 for (int[] edge : edges) {
43 int U = edge[0], V = edge[1], edgeNodes = edge[2];
44 int movesLeftFromU = Math.max(0, maxMoves - distances[U]);
45 int movesLeftFromV = Math.max(0, maxMoves - distances[V]);
46 // The new reachable nodes are limited by the edge nodes and sum of moves we can spend from both sides of the edge
47 reachableNodesCount += Math.min(edgeNodes, movesLeftFromU + movesLeftFromV);
48 }
49
50 return reachableNodesCount; // Total count of reachable nodes
51 }
52}
53
1#include <vector>
2#include <queue>
3#include <cstring>
4
5class Solution {
6public:
7 int reachableNodes(std::vector<std::vector<int>>& edges, int maxMoves, int nodeCount) {
8 using PII = std::pair<int, int>; // Alias for the pair type used.
9
10 // Graph representation where each node points to its neighbors with the edge weight.
11 std::vector<std::vector<PII>> graph(nodeCount);
12 for (const auto& edge : edges) {
13 int from = edge[0], to = edge[1], weight = edge[2] + 1; // Weight incremented to represent 'new' nodes within the edge.
14 graph[from].emplace_back(to, weight);
15 graph[to].emplace_back(from, weight);
16 }
17
18 // Priority queue to perform the Dijkstra's algorithm.
19 std::priority_queue<PII, std::vector<PII>, std::greater<PII>> priorityQueue;
20 priorityQueue.emplace(0, 0); // Start with node 0 and distance 0.
21
22 // Initialize distances array with infinity.
23 int distances[nodeCount];
24 std::memset(distances, 0x3f, sizeof distances);
25 distances[0] = 0; // Distance to the starting node is 0.
26
27 // Dijkstra's algorithm to find shortest paths from node 0 to all other nodes.
28 while (!priorityQueue.empty()) {
29 auto [currentDistance, currentNode] = priorityQueue.top();
30 priorityQueue.pop();
31
32 // Update distances to the neighboring nodes if a shorter path is found.
33 for (const auto& [neighbor, weight] : graph[currentNode]) {
34 if (currentDistance + weight < distances[neighbor]) {
35 distances[neighbor] = currentDistance + weight;
36 priorityQueue.emplace(distances[neighbor], neighbor);
37 }
38 }
39 }
40
41 // After Dijkstra's, count how many nodes are reachable.
42 int reachableNodesCount = 0;
43 for (int distance : distances) {
44 if (distance <= maxMoves) {
45 reachableNodesCount++;
46 }
47 }
48
49 // Count how many 'new' nodes within the edges are reachable.
50 for (const auto& edge : edges) {
51 int from = edge[0], to = edge[1], count = edge[2];
52
53 // Calculate how many 'new' nodes can be visited from both sides of the edge.
54 int reachableFromEnd = std::min(count, std::max(0, maxMoves - distances[from]));
55 int reachableFromStart = std::min(count, std::max(0, maxMoves - distances[to]));
56
57 // The minimum of the total count and the sum of reachables from both ends gives the total new nodes reachable.
58 reachableNodesCount += std::min(count, reachableFromEnd + reachableFromStart);
59 }
60
61 return reachableNodesCount;
62 }
63};
64
1function reachableNodes(edges: number[][], maxMoves: number, nodeCount: number): number {
2 // Type alias for the pair used to represent edge weight and neighbor.
3 type Pair = [number, number];
4
5 // Graph representation where each node points to its neighbors with the edge weight.
6 let graph: Pair[][] = Array.from({ length: nodeCount }, () => []);
7 for (const edge of edges) {
8 let from = edge[0], to = edge[1], weight = edge[2] + 1; // Increment weight to represent 'new' nodes within the edge.
9 graph[from].push([to, weight]);
10 graph[to].push([from, weight]);
11 }
12
13 // Priority queue to perform Dijkstra's algorithm. Using an array to simulate a min-heap priority queue.
14 let priorityQueue: Pair[] = [];
15 function pushHeap(pair: Pair) {
16 priorityQueue.push(pair);
17 priorityQueue.sort((a, b) => a[0] - b[0]); // Ensure the smallest distance is at the end of the array.
18 }
19 function popHeap() {
20 return priorityQueue.pop(); // Removes and returns the pair with the smallest distance.
21 }
22
23 // Initialize the starting point for Dijkstra's algorithm.
24 pushHeap([0, 0]); // Start with node 0 and distance 0.
25
26 // Initialize distances array with a large number to simulate Infinity.
27 let distances: number[] = new Array(nodeCount).fill(Number.MAX_SAFE_INTEGER);
28 distances[0] = 0; // Distance to the starting node is 0.
29
30 // Dijkstra's algorithm to find shortest paths from node 0 to all other nodes.
31 while (priorityQueue.length > 0) {
32 let [currentDistance, currentNode] = popHeap()!;
33
34 // Update distances to the neighboring nodes if a shorter path is found.
35 for (const [neighbor, weight] of graph[currentNode]) {
36 if (currentDistance + weight < distances[neighbor]) {
37 distances[neighbor] = currentDistance + weight;
38 pushHeap([distances[neighbor], neighbor]);
39 }
40 }
41 }
42
43 // Count how many nodes are reachable within the maxMoves.
44 let reachableNodesCount = distances.filter(distance => distance <= maxMoves).length;
45
46 // Count how many 'new' nodes within the edges are reachable.
47 for (const edge of edges) {
48 let from = edge[0], to = edge[1], count = edge[2];
49
50 // Calculate how many 'new' nodes can be visited from both sides of the edge.
51 let reachableFromFrom = Math.min(count, Math.max(0, maxMoves - distances[from]));
52 let reachableFromTo = Math.min(count, Math.max(0, maxMoves - distances[to]));
53
54 // Add to the total count; this is the number of 'new' nodes reachable from both ends of the edge.
55 reachableNodesCount += Math.min(count, reachableFromFrom + reachableFromTo);
56 }
57
58 return reachableNodesCount;
59}
60
Time and Space Complexity
Time Complexity:
The given code performs a modified Dijkstra's algorithm to find the smallest number of moves required to reach each node and then calculates how many nodes can be reached and how many new edges are reachable within the maximum number of moves.
-
Building the graph: The construction of the graph
g
is done inO(E)
time whereE
is the number of edges because we iterate through each edge once. -
Priority Queue Operations (Dijkstra's algorithm): The priority queue is used to keep track of the nodes to visit next based on the smallest distance. Each insertion into the priority queue is
O(logN)
whereN
is the number of nodes, and we might perform this operation for each edge in the worst case. So, this step takesO(ElogN)
time. -
Distances Calculation: This part checks each edge and considers the minimum between an actual counter and the maximum moves minus the distance to the current nodes (
u
andv
). Each edge is checked once, so this step isO(E)
.
Therefore, the total time complexity is dominated by the Dijkstra's part, which is O(ElogN)
.
Space Complexity:
-
Graph Representation: The adjacency list
g
stores at most2E
pairs for the bidirectional edges, hence takingO(E)
space. -
Distance Array: The array
dist
keeps distances forN
nodes, thusO(N)
space is used. -
Priority Queue: At most, the heap queue could store all nodes simultaneously, which would again require
O(N)
space.
The final space complexity combines the above requirements, resulting in O(E + N)
due to storing both the graph and the other data structures.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue