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.

Solution Approach

The implementation of the problem follows the intuition we described earlier. The details are as follows:

  1. 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.

  2. 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.

  3. 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 the dist list and the queue accordingly).

  4. 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 the maxMoves minus the distance to each end of the edge.
  5. 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 each u, v, cnt in the edges list, we calculate the sum of reachable new nodes from both u and v, and add the smaller of the cnt and this sum to ans. 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.

💪
Level Up Your
Algo Skills

Example 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 and 1, respectively, which are less than or equal to maxMoves (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 since maxMoves - dist[1] = 2 - 2 = 0 moves left, so no new nodes can be visited from that edge on the side of node 1.

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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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.

  1. Building the graph: The construction of the graph g is done in O(E) time where E is the number of edges because we iterate through each edge once.

  2. 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) where N is the number of nodes, and we might perform this operation for each edge in the worst case. So, this step takes O(ElogN) time.

  3. 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 and v). Each edge is checked once, so this step is O(E).

Therefore, the total time complexity is dominated by the Dijkstra's part, which is O(ElogN).

Space Complexity:

  1. Graph Representation: The adjacency list g stores at most 2E pairs for the bidirectional edges, hence taking O(E) space.

  2. Distance Array: The array dist keeps distances for N nodes, thus O(N) space is used.

  3. 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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫