Reachable Nodes In Subdivided Graph - Leetcode Solution

Problem Statement: Given an undirected graph represented by an adjacency list and an integer maximumMoves, you need to find the number of nodes that are reachable from the source node 0 after exactly maximumMoves moves. If maximumMoves is even, the source node is at position 0, otherwise it is at position 1.

Solution: We can solve this problem using BFS on the given adjacency list. In each BFS level, we will consider all the nodes that can be reached in exactly current_move moves from the source node. We can keep track of the nodes that are visited in each BFS level using a Boolean array, and add them to a set of reachable nodes after exactly maximumMoves moves.

The source node will be at position 0 when maximumMoves is even, and at position 1 when maximumMoves is odd. We can start BFS from the source node and calculate the number of reachable nodes after exactly maximumMoves moves.

Algorithm:

1. Initialize an empty set reachableNodes to store the nodes that are reachable after exactly maximumMoves moves.
2. Initialize a Boolean array visitedNodes to keep track of visited nodes in each BFS level.
3. Initialize a queue and add the source node to it.
4. Initialize a variable current_move to 0.
5. While the queue is not empty and current_move <= maximumMoves: a. Get the size of the queue as qSize. b. Initialize visitedNodes to False for all nodes. c. For i from 1 to qSize: i. Dequeue a node from the queue. ii. If the node has not been visited in this BFS level, mark it as visited and add it to reachableNodes. iii. For each neighbor of the node, if it has not been visited yet, add it to the queue and mark it as visited. d. Increment current_move by 1.
6. Return the size of the reachableNodes set.

Time Complexity: The time complexity of BFS is O(V+E), where V is the number of nodes and E is the number of edges in the graph. In this problem, we need to perform BFS for each step up to maximumMoves. Therefore, the time complexity of the algorithm is O(maximumMoves*(V+E)).

Space Complexity: The space complexity of the algorithm is O(V+E) for the adjacency list and visitedNodes array, O(maximumMoves) for the queue, and O(V) for the reachableNodes set. Therefore, the space complexity is O(maximumMoves + V + E).

Code:

def reachableNodes(edges, maximumMoves, n): adjList = [set() for _ in range(n)] for u, v, w in edges: adjList[u].add((v, w+1)) adjList[v].add((u, w+1))

source = 0 if maximumMoves%2 == 0 else 1
queue = [(source, 0)]
visited = {source: 0}
reachableNodes = set()

while queue:
    node, distance = queue.pop(0)
    if distance > maximumMoves:
        break
    if node not in reachableNodes:
        reachableNodes.add(node)
    for neighbor, edgeLength in adjList[node]:
        if neighbor in visited and visited[neighbor] <= distance + edgeLength:
            continue
        visited[neighbor] = distance + edgeLength
        if distance + edgeLength <= maximumMoves:
            queue.append((neighbor, distance + edgeLength))
            reachableNodes.add(neighbor)

return len(reachableNodes)

1