Metro Transfer Capacity Map

Array Easy 0 views

Like24

The transit team is auditing emergency bulletin flows through the underground during maintenance closures. Stations are indexed 0 to n-1, and you're given a log of bidirectional tunnels. When a bulletin issues at an origin station, crews relay it to all neighbors. Your task in Metro Transfer Capacity Map is to count how many distinct stations hear the message while avoiding any Suspended Stations.

The "secret sauce" here is Graph Traversal with Node Exclusions. Explore the network using BFS or DFS, but never pass through any station in the suspended_stations list. Any path hitting a closed stop is blocked. The origin is always open and counts as one recipient, and repeated tunnels are treated as a single link. Traversal stops once no more open stations can be reached. This audit helps the team adjust staffing during partial closures! It’s a vital skill for anyone building robust routing or real-time event-management systems.

When the task involves connectivity or route cost, build adjacency carefully and guard against revisiting stale states. Use a visited or best-distance structure to avoid repeated work, and ensure unreachable scenarios return the required fallback value instead of partial traversal results.

Examples

Example 1

Input

n = 6, lines = [[0,2],[2,3],[3,1],[1,5],[5,4]], start = 3, suspended_stations = [1,5]

Output

Explanation

The team can reach stations 3, 2, and 0 but cannot pass through the suspended stops.

Example 2

Input

n = 7, lines = [[0,1],[1,2],[2,3],[3,4],[1,5],[5,6]], start = 0, suspended_stations = [4]

Output

Explanation

Stations 0, 1, 2, 3, 5, and 6 receive the update while station 4 remains closed.

Example 3

Input

n = 4, lines = [[0,1],[1,2]], start = 2, suspended_stations = [0,1]

Output

Explanation

Only the origin station is open, so the message does not travel anywhere else.

Algorithm Flow

Recommendation Algorithm Flow for Metro Transfer Capacity Map - Budibadu

Best Answers

java

import java.util.*;

class Solution {
    public int metro_transfer_capacity_map(int n, int[][] lines, int start, int[] suspended_stations) {
        Set<Integer> suspended = new HashSet<>();
        for (int s : suspended_stations) suspended.add(s);
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] line : lines) {
            int u = line[0], v = line[1];
            if (!suspended.contains(u) && !suspended.contains(v)) {
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
        }
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int neighbor : adj.get(curr)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return visited.size();
    }
}

javascript

function metro_transfer_capacity_map(n, lines, start, suspended_stations) {
    const suspended = new Set(suspended_stations);
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of lines) {
        if (!suspended.has(u) && !suspended.has(v)) {
            adj[u].push(v);
            adj[v].push(u);
        }
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const curr = queue.shift();
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

php

<?php
function metro_transfer_capacity_map($n, $lines, $start, $suspended_stations) {
    $adj = array_fill(0, $n, []);
    foreach ($lines as $line) {
        $u = $line[0]; $v = $line[1];
        if (!in_array($u, $suspended_stations) && !in_array($v, $suspended_stations)) {
            $adj[$u][] = $v;
            $adj[$v][] = $u;
        }
    }
    $visited = [$start => true];
    $queue = [$start];
    while (!empty($queue)) {
        $curr = array_shift($queue);
        foreach ($adj[$curr] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = $neighbor;
            }
        }
    }
    return count($visited);
}
?>

python

from typing import List
from collections import deque

def metro_transfer_capacity_map(n: int, lines: List[List[int]], start: int, suspended_stations: List[int]) -> int:
    suspended = set(suspended_stations)
    adj = [[] for _ in range(n)]
    for u, v in lines:
        if u not in suspended and v not in suspended:
            adj[u].append(v)
            adj[v].append(u)
    visited = {start}
    queue = deque([start])
    while queue:
        curr = queue.popleft()
        for neighbor in adj[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return len(visited)

rust

use std::collections::{HashSet, VecDeque};

pub fn metro_transfer_capacity_map(n: i32, lines: Vec<Vec<i32>>, start: i32, suspended_stations: Vec<i32>) -> i32 {
    let suspended: HashSet<i32> = suspended_stations.into_iter().collect();
    let mut adj = vec![vec![]; n as usize];
    for line in lines {
        let u = line[0];
        let v = line[1];
        if !suspended.contains(&u) && !suspended.contains(&v) {
            adj[u as usize].push(v);
            adj[v as usize].push(u);
        }
    }
    let mut visited = HashSet::new();
    visited.insert(start);
    let mut queue = VecDeque::new();
    queue.push_back(start);
    while let Some(curr) = queue.pop_front() {
        for &neighbor in &adj[curr as usize] {
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                queue.push_back(neighbor);
            }
        }
    }
    visited.len() as i32
}

typescript

function metro_transfer_capacity_map(n: number, lines: number[][], start: number, suspended_stations: number[]): number {
    const suspended = new Set(suspended_stations);
    const adj: number[][] = Array.from({length: n}, () => []);
    for (const [u, v] of lines) {
        if (!suspended.has(u) && !suspended.has(v)) {
            adj[u].push(v);
            adj[v].push(u);
        }
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const curr = queue.shift()!;
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Metro Transfer Capacity Map

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Array Problems

Longest Consecutive Sequence

Garden Relay Count

Lantern Stall Picks

Festival Stall Order

Studio Lighting Slots

Seaport Ferry Gate Control

Comments (0)

Join the Discussion