Reachable Nodes In Subdivided Graph

Tested Python solution for LeetCode 882 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 882, Hard. Topics: Graph Theory, Heap (Priority Queue), Shortest Path, Dijkstra’s Algorithm. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 22 parametrized pytest cases, and a playground notebook:

lcpy gen -n 882   # by problem number
lcpy gen -s reachable_nodes_in_subdivided_graph   # by problem name

​

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] = [u<sub>i</sub>, v<sub>i</sub>, cnt<sub>i</sub>] indicates that there is an edge between nodes u<sub>i</sub> and v<sub>i</sub> in the original graph, and cnt<sub>i</sub> is the total number of new nodes that you will subdivide the edge into. Note that cnt<sub>i</sub> == 0 means you will not subdivide the edge.

To subdivide the edge [u<sub>i</sub>, v<sub>i</sub>], replace it with (cnt<sub>i</sub> + 1) new edges and cnt<sub>i</sub> new nodes. The new nodes are x<sub>1</sub>, x<sub>2</sub>, …, x<sub>cnt<sub>i</sub></sub>, and the new edges are [u<sub>i</sub>, x<sub>1</sub>], [x<sub>1</sub>, x<sub>2</sub>], [x<sub>2</sub>, x<sub>3</sub>], …, [x<sub>cnt<sub>i</sub>-1</sub>, x<sub>cnt<sub>i</sub></sub>], [x<sub>cnt<sub>i</sub></sub>, v<sub>i</sub>].

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.

​

Examples

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.

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

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, 10⁴)
• edges[i].length == 3
• 0 <= u_i < v_i < n
• There are no multiple edges in the graph.
• 0 <= cnt_i <= 10⁴
• 0 <= maxMoves <= 10⁹
• 1 <= n <= 3000

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

import heapq


class Solution:
    # Time: O(E log V)
    # Space: O(V + E)
    def reachable_nodes(self, edges: list[list[int]], max_moves: int, n: int) -> int:
        adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
        for u, v, cnt in edges:
            adj[u].append((v, cnt))
            adj[v].append((u, cnt))

        unreachable = max_moves + 1
        dist = [unreachable] * n
        dist[0] = 0
        heap: list[tuple[int, int]] = [(0, 0)]
        while heap:
            d, node = heapq.heappop(heap)
            if d > dist[node]:
                continue
            for nxt, cnt in adj[node]:
                nd = d + cnt + 1
                if nd < dist[nxt]:
                    dist[nxt] = nd
                    heapq.heappush(heap, (nd, nxt))

        reachable = sum(1 for d in dist if d <= max_moves)
        for u, v, cnt in edges:
            head = max(0, max_moves - dist[u])
            tail = max(0, max_moves - dist[v])
            reachable += min(cnt, head + tail)
        return reachable

​

Complexity

Time	Space
O(E log V)	O(V + E)

​

Tags