LeetCode 882: Reachable Nodes In Subdivided Graph

Problem Restatement

We are given an undirected graph with original nodes numbered from 0 to n - 1.

Each edge is written as:

[u, v, cnt]

This means the original edge between u and v is subdivided by adding cnt new nodes between them.

For example:

[0, 1, 3]

becomes:

0 - x1 - x2 - x3 - 1

So moving from 0 to 1 through this edge takes cnt + 1 moves.

Starting from node 0, we can make at most maxMoves moves.

Return how many nodes are reachable in the new subdivided graph. This includes both original nodes and new subdivided nodes. The problem defines a node as reachable if its distance from node 0 is at most maxMoves.

Input and Output

Function shape:

def reachableNodes(
    self,
    edges: list[list[int]],
    maxMoves: int,
    n: int
) -> int:
    ...

Examples

Example 1:

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13

The edge [0,1,10] has 10 new nodes.

The edge [0,2,1] has 1 new node.

The edge [1,2,2] has 2 new nodes.

We count every original node reachable from 0, and every subdivided node reachable along each edge.

Example 2:

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
Output: 23

The shortest distances between original nodes use edge weights cnt + 1.

For example, edge [0,1,4] takes 5 moves to cross.

With 10 moves, all four original nodes are reachable, and all subdivided nodes on the edges are reachable, so the answer is 23.

First Thought: Build the Full Graph

A direct idea is to explicitly create every new node.

For edge:

[u, v, cnt]

we create nodes:

x1, x2, ..., xcnt

and edges:

u - x1 - x2 - ... - xcnt - v

Then we can run BFS or Dijkstra from node 0 and count nodes with distance at most maxMoves.

This is logically simple, but it can create too many nodes.

If many edges have large cnt, the expanded graph becomes much larger than the input graph.

Key Insight

We do not need to build the subdivided graph.

Each original edge [u, v, cnt] behaves like a weighted edge of cost:

cnt + 1

between original nodes u and v.

So first, compute shortest distances from node 0 to every original node using Dijkstra.

Then count:

1. Original nodes whose shortest distance is at most maxMoves.
2. Subdivided nodes reachable from either side of each original edge.

For an edge [u, v, cnt], suppose:

dist[u] = shortest distance from 0 to u
dist[v] = shortest distance from 0 to v

From the u side, we can enter at most:

max(0, maxMoves - dist[u])

subdivided nodes.

From the v side, we can enter at most:

max(0, maxMoves - dist[v])

subdivided nodes.

But the edge only has cnt subdivided nodes, so the number reachable on this edge is:

min(
    cnt,
    max(0, maxMoves - dist[u]) + max(0, maxMoves - dist[v])
)

This avoids double counting overlap from both sides.

Algorithm

Build a weighted adjacency list using only the original nodes.

For each edge [u, v, cnt], add:

u -> v with weight cnt + 1
v -> u with weight cnt + 1

Run Dijkstra from node 0.

Then initialize:

answer = number of original nodes with dist[node] <= maxMoves

For each original edge [u, v, cnt]:

1. Compute how many subdivided nodes are reachable from u.
2. Compute how many subdivided nodes are reachable from v.
3. Add the capped total:

answer += min(cnt, from_u + from_v)

Return answer.

Walkthrough

Use:

edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]]
maxMoves = 10
n = 4

Convert each subdivided edge into a weighted edge:

Dijkstra gives:

All 4 original nodes are reachable.

Now count subdivided nodes:

Total:

original nodes: 4
subdivided nodes: 4 + 6 + 8 + 1 = 19
answer: 23

Correctness

Dijkstra computes the shortest distance from node 0 to every original node because all weighted edge costs are positive. Each original edge [u, v, cnt] has traversal cost cnt + 1, which exactly matches the number of moves needed to go from u to v through all subdivided nodes.

An original node is reachable exactly when its shortest distance is at most maxMoves, so counting such nodes is correct.

Now consider one original edge [u, v, cnt].

If u is reachable with dist[u] moves, then after reaching u, we have maxMoves - dist[u] moves left. Each remaining move can advance one subdivided node along the edge from the u side. Therefore, the number reachable from the u side is max(0, maxMoves - dist[u]), capped by cnt.

The same reasoning applies from the v side.

Some subdivided nodes may be reachable from both sides. Since the edge contains only cnt subdivided nodes, the number of distinct reachable subdivided nodes on this edge is the smaller of cnt and the sum of the reachable counts from both sides.

Each subdivided node belongs to exactly one original edge, so summing this value over all edges counts every reachable subdivided node exactly once.

Therefore, the algorithm returns the exact number of reachable nodes in the subdivided graph.

Complexity

Let:

V = n
E = len(edges)

Implementation

import heapq
from collections import defaultdict

class Solution:
    def reachableNodes(
        self,
        edges: list[list[int]],
        maxMoves: int,
        n: int
    ) -> int:
        graph = defaultdict(list)

        for u, v, cnt in edges:
            weight = cnt + 1
            graph[u].append((v, weight))
            graph[v].append((u, weight))

        dist = [float("inf")] * n
        dist[0] = 0

        heap = [(0, 0)]

        while heap:
            curr_dist, node = heapq.heappop(heap)

            if curr_dist > dist[node]:
                continue

            for nei, weight in graph[node]:
                next_dist = curr_dist + weight

                if next_dist < dist[nei]:
                    dist[nei] = next_dist
                    heapq.heappush(heap, (next_dist, nei))

        answer = 0

        for d in dist:
            if d <= maxMoves:
                answer += 1

        for u, v, cnt in edges:
            from_u = 0
            if dist[u] <= maxMoves:
                from_u = maxMoves - dist[u]

            from_v = 0
            if dist[v] <= maxMoves:
                from_v = maxMoves - dist[v]

            answer += min(cnt, from_u + from_v)

        return answer

Code Explanation

We build the graph over original nodes only:

for u, v, cnt in edges:
    weight = cnt + 1
    graph[u].append((v, weight))
    graph[v].append((u, weight))

The weight is cnt + 1 because crossing the whole subdivided edge requires passing through cnt new nodes and then reaching the other original node.

The distance array stores shortest distances from node 0:

dist = [float("inf")] * n
dist[0] = 0

Dijkstra processes the currently closest known original node:

curr_dist, node = heapq.heappop(heap)

If the heap entry is outdated, we skip it:

if curr_dist > dist[node]:
    continue

Then we relax each neighboring original node:

next_dist = curr_dist + weight

if next_dist < dist[nei]:
    dist[nei] = next_dist
    heapq.heappush(heap, (next_dist, nei))

After shortest distances are known, we count reachable original nodes:

for d in dist:
    if d <= maxMoves:
        answer += 1

Then we count reachable subdivided nodes on each edge:

answer += min(cnt, from_u + from_v)

The min prevents counting more subdivided nodes than the edge actually contains.

Testing

def run_tests():
    s = Solution()

    assert s.reachableNodes(
        [[0, 1, 10], [0, 2, 1], [1, 2, 2]],
        6,
        3
    ) == 13

    assert s.reachableNodes(
        [[0, 1, 4], [1, 2, 6], [0, 2, 8], [1, 3, 1]],
        10,
        4
    ) == 23

    assert s.reachableNodes(
        [[1, 2, 4], [1, 4, 5], [1, 3, 1], [2, 3, 4], [3, 4, 5]],
        17,
        5
    ) == 1

    assert s.reachableNodes(
        [],
        5,
        1
    ) == 1

    assert s.reachableNodes(
        [[0, 1, 0]],
        1,
        2
    ) == 2

    print("all tests passed")

run_tests()

Test meaning: