# Reachable Nodes In Subdivided Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/reachable-nodes-in-subdivided-graph)
Canonical: https://scaleengineer.com/dsa/problems/reachable-nodes-in-subdivided-graph
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
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:**

![](https://assets.glich.co/dsa/reachable-nodes-in-subdivided-graph/image0.png) 

**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 == 3`
* `0 <= ui < vi < n`
* There are **no multiple edges** in the graph.
* `0 <= cnti <= 104`
* `0 <= maxMoves <= 109`
* `1 <= n <= 3000`

# Approaches
## Brute-Force: Explicit Graph Construction and BFS
This approach involves constructing the entire subdivided graph explicitly in memory. After the full graph is built, we can run a standard Breadth-First Search (BFS) starting from node 0 to find all nodes reachable within `maxMoves`. Since all new edges in the subdivided graph have a length of 1, BFS is a suitable algorithm for finding the shortest paths.
**Time:** O(N' + E'), where N' and E' are the number of nodes and edges in the full subdivided graph. This can be up to O(10^8) in the worst case, which is too slow and will result in a 'Time Limit Exceeded' error. · **Space:** O(N' + E'), where N' is the number of nodes and E' is the number of edges in the subdivided graph. In the worst case, `N' = n + sum(cnt_i)` and `E' = sum(cnt_i + 1)`, which can be up to O(10^8), leading to a 'Memory Limit Exceeded' error.
**Pros:** Simple to understand and implement.; Directly models the problem statement without complex logic.
**Cons:** Extremely high memory usage. The number of nodes and edges in the subdivided graph can be up to O(10^8), which will exceed typical memory limits.; Very slow. The time complexity is proportional to the size of the subdivided graph, which is too large for the given constraints, leading to a 'Time Limit Exceeded' error.
### Explanation
The core idea is to translate the problem description directly into a data structure. We create a new graph that includes all original nodes and all new subdivided nodes. This approach is straightforward but highly inefficient due to the potential size of the new graph.

```java
// NOTE: This approach is conceptually correct but will fail due to Time Limit Exceeded (TLE)
// and Memory Limit Exceeded (MLE) on larger test cases.
class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        // 1. Build the explicit subdivided graph
        Map<Integer, List<Integer>> adj = new HashMap<>();
        int currentNodeId = n;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            int prev = u;
            for (int i = 0; i < cnt; i++) {
                adj.computeIfAbsent(prev, k -> new ArrayList<>()).add(currentNodeId);
                adj.computeIfAbsent(currentNodeId, k -> new ArrayList<>()).add(prev);
                prev = currentNodeId;
                currentNodeId++;
            }
            adj.computeIfAbsent(prev, k -> new ArrayList<>()).add(v);
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(prev);
        }

        // 2. Run BFS to find all reachable nodes
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> dist = new HashMap<>();

        queue.offer(0);
        dist.put(0, 0);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            int d = dist.get(u);

            if (d >= maxMoves) {
                continue;
            }

            if (adj.containsKey(u)) {
                for (int v : adj.get(u)) {
                    if (!dist.containsKey(v)) {
                        dist.put(v, d + 1);
                        queue.offer(v);
                    }
                }
            }
        }

        // 3. The number of reachable nodes is the number of nodes we found a path to.
        return dist.size();
    }
}
```
### Algorithm
- **Graph Construction:**
  1. Initialize an adjacency list for the new, large graph.
  2. Create a counter for new node IDs, starting from `n`.
  3. Iterate through each edge `[u, v, cnt]` from the input `edges`.
  4. For each edge, create `cnt` new nodes. Connect `u` to the first new node, chain the new nodes together, and connect the last new node to `v`. Each of these new connections is an edge of weight 1.
  5. Add these new edges to the adjacency list, making sure they are undirected.
- **Breadth-First Search (BFS):**
  1. After the full graph is built, initialize a queue for BFS and a `dist` map to store the shortest distance from node 0 to any other node.
  2. Add node 0 to the queue and set its distance to 0 in the `dist` map: `dist[0] = 0`.
  3. While the queue is not empty, dequeue a node `u`.
  4. Let `d` be the distance to `u`. If `d` is already equal to `maxMoves`, we cannot explore its neighbors, so continue.
  5. For each neighbor `v` of `u`, if `v` has not been visited (i.e., not in `dist` map), add it to the `dist` map with distance `d + 1` and enqueue `v`.
- **Count Nodes:**
  1. The BFS process populates the `dist` map with all nodes reachable from node 0 within `maxMoves`.
  2. The total number of reachable nodes is simply the final size of the `dist` map.

## Optimized Approach using Dijkstra's Algorithm
This approach avoids building the large subdivided graph. Instead, it recognizes that the problem can be solved by first finding the shortest paths from node 0 to all other *original* nodes. The subdivided edges are treated as having a weight equal to the number of new nodes plus one. After finding these shortest paths using Dijkstra's algorithm, we can calculate how many subdivided nodes on each edge are reachable.
**Time:** O(E log N), where E is the number of original edges and N is the number of original nodes. This is dominated by Dijkstra's algorithm with a priority queue. Given the constraints, this is very efficient. · **Space:** O(N + E), where N is the number of original nodes and E is the number of original edges. This is for storing the adjacency list, the distance array, and the priority queue, which is well within memory limits.
**Pros:** Highly efficient in both time and space.; Avoids the creation of the massive subdivided graph, working only with the original graph's dimensions.; Correctly handles all cases within the given constraints.
**Cons:** The logic is more complex than the brute-force approach, requiring understanding of Dijkstra's algorithm and insights into how to count the subdivided nodes without creating them.
### Explanation
The key insight is that we only need to know the shortest distance to the original nodes (`0` to `n-1`) to determine reachability. The subdivided nodes don't provide any shortcuts; they only increase path lengths. By working on the much smaller original graph, we can solve the problem efficiently.

```java
class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        // 1. Build adjacency list for the original graph with weighted edges
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{v, cnt + 1});
            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new int[]{u, cnt + 1});
        }

        // 2. Run Dijkstra's algorithm from node 0
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        // PriorityQueue stores {distance, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0];
            int u = curr[1];

            if (d > dist[u]) {
                continue;
            }

            if (adj.containsKey(u)) {
                for (int[] neighbor : adj.get(u)) {
                    int v = neighbor[0];
                    int weight = neighbor[1];
                    if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        pq.offer(new int[]{dist[v], v});
                    }
                }
            }
        }

        // 3. Calculate total reachable nodes
        int totalReachableNodes = 0;

        // Count reachable original nodes
        for (int i = 0; i < n; i++) {
            if (dist[i] <= maxMoves) {
                totalReachableNodes++;
            }
        }

        // Count reachable subdivided nodes
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            
            long movesFromU = (dist[u] == Integer.MAX_VALUE) ? 0 : maxMoves - dist[u];
            long movesFromV = (dist[v] == Integer.MAX_VALUE) ? 0 : maxMoves - dist[v];
            
            long reachableOnEdge = Math.max(0, movesFromU) + Math.max(0, movesFromV);
            
            totalReachableNodes += Math.min(cnt, reachableOnEdge);
        }

        return totalReachableNodes;
    }
}
```
### Algorithm
- **Graph Representation:**
  1. Construct an adjacency list for the *original* graph. The nodes are `0` to `n-1`.
  2. For each edge `[u, v, cnt]` in the input, treat it as a weighted edge where the weight is `cnt + 1`. This weight represents the distance between `u` and `v` in the subdivided graph.
- **Dijkstra's Algorithm:**
  1. Run Dijkstra's algorithm starting from source node 0 on this weighted graph.
  2. Use a priority queue to efficiently find the node with the smallest distance to visit next.
  3. Maintain a `dist` array to store the shortest distance from node 0 to every other original node `i`.
- **Calculate Reachable Nodes:**
  1. Initialize a counter `totalReachableNodes` to 0.
  2. **Count original nodes:** Iterate through all original nodes `i` from `0` to `n-1`. If `dist[i] <= maxMoves`, it means node `i` is reachable, so increment the counter.
  3. **Count subdivided nodes:** Iterate through each original edge `[u, v, cnt]`.
     - Calculate the number of moves remaining after reaching `u`: `movesFromU = max(0, maxMoves - dist[u])`.
     - Calculate the number of moves remaining after reaching `v`: `movesFromV = max(0, maxMoves - dist[v])`.
     - The number of subdivided nodes on this edge that can be reached from either end is `movesFromU + movesFromV`.
     - This value cannot exceed the total number of subdivided nodes on the edge, which is `cnt`. So, the number of reachable subdivided nodes on this edge is `min(cnt, movesFromU + movesFromV)`.
     - Add this number to `totalReachableNodes`.
- **Return Result:**
  1. The final value of `totalReachableNodes` is the answer.

# Solutions
### Java

```java
class Solution {
public
  int reachableNodes(int[][] edges, int maxMoves, int n) {
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, e->new ArrayList<>());
    for (var e : edges) {
      int u = e[0], v = e[1], cnt = e[2] + 1;
      g[u].add(new int[]{v, cnt});
      g[v].add(new int[]{u, cnt});
    }
    int[] dist = new int[n];
    Arrays.fill(dist, 1 << 30);
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] - b[0]);
    q.offer(new int[]{0, 0});
    dist[0] = 0;
    while (!q.isEmpty()) {
      var p = q.poll();
      int d = p[0], u = p[1];
      for (var nxt : g[u]) {
        int v = nxt[0], cnt = nxt[1];
        if (d + cnt < dist[v]) {
          dist[v] = d + cnt;
          q.offer(new int[]{dist[v], v});
        }
      }
    }
    int ans = 0;
    for (int d : dist) {
      if (d <= maxMoves) {
        ++ans;
      }
    }
    for (var e : edges) {
      int u = e[0], v = e[1], cnt = e[2];
      int a = Math.min(cnt, Math.max(0, maxMoves - dist[u]));
      int b = Math.min(cnt, Math.max(0, maxMoves - dist[v]));
      ans += Math.min(cnt, a + b);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int reachableNodes(vector<vector<int>> &edges, int maxMoves, int n) {
    using pii = pair<int, int>;
    vector<vector<pii>> g(n);
    for (auto &e : edges) {
      int u = e[0], v = e[1], cnt = e[2] + 1;
      g[u].emplace_back(v, cnt);
      g[v].emplace_back(u, cnt);
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.emplace(0, 0);
    int dist[n];
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    while (!q.empty()) {
      auto [d, u] = q.top();
      q.pop();
      for (auto &[v, cnt] : g[u]) {
        if (d + cnt < dist[v]) {
          dist[v] = d + cnt;
          q.emplace(dist[v], v);
        }
      }
    }
    int ans = 0;
    for (int &d : dist)
      ans += d <= maxMoves;
    for (auto &e : edges) {
      int u = e[0], v = e[1], cnt = e[2];
      int a = min(cnt, max(0, maxMoves - dist[u]));
      int b = min(cnt, max(0, maxMoves - dist[v]));
      ans += min(cnt, a + b);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int: g = defaultdict(list) for u, v, cnt in edges: g[u]. append((v, cnt + 1)) g[v]. append((u, cnt + 1)) q = [(0, 0)] dist = [0] + [inf] * n while q: d, u = heappop(q) for v, cnt in g[u]: if (t: = d + cnt) < dist[v]: dist[v] = t q . append((t, v)) ans = sum(d <= maxMoves for d in dist) for u, v, cnt in edges: a = min(cnt, max(0, maxMoves - dist[u])) b = min(cnt, max(0, maxMoves - dist[v])) ans += min(cnt, a + b) return ans

```