Metro Transfer Capacity Map

Published at05 Jan 2026

Graph BFS Easy 26 views

Like24

You can think of this as a small game with a very specific goal. In Metro Transfer Capacity Map, you are trying to work toward the right number by following one clear idea.

Here, you start with one piece of information and turn it into something cleaner or more useful. You might keep only certain items, change their shape, or fix how text looks. The important part is to follow the steps in the right order. If you do that carefully, the final result comes out just the way the problem expects.

For example, if the input is n = 6, lines = [[0,2],[2,3],[3,1],[1,5],[5,4]], start = 3, suspended_stations = [1,5], the answer is 3. The team can reach stations 3, 2, and 0 but cannot pass through the suspended stops. Another example is n = 7, lines = [[0,1],[1,2],[2,3],[3,4],[1,5],[5,6]], start = 0, suspended_stations = [4], which gives 6. Stations 0, 1, 2, 3, 5, and 6 receive the update while station 4 remains closed.

This is a friendly practice problem, but it still rewards careful reading. The key is doing the steps in the right order and not changing things you should keep.

Example Input & Output

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

Solution Approach

This problem asks us to count how many stations the team can reach while skipping suspended stations. The lines form an undirected graph, and we must build the graph without any edge that touches a suspended station, then count the connected component of the start.

The key is that a suspended station cannot be part of any usable route. So when we build the adjacency list, we drop any line whose either endpoint is suspended, effectively removing those nodes and their edges from the graph.

Here is the implementation:

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;
}

We put the suspended stations in a set for fast lookup. While building the graph, we only add an edge if neither endpoint is suspended. This automatically isolates the suspended stations and removes any route through them. Then a standard BFS from the start counts the reachable component.

Let us trace n = 6, lines = [[0,2],[2,3],[3,1],[1,5],[5,4]], start = 3, suspended_stations = [1,5]. Stations 1 and 5 are suspended, so the usable edges are [0,2] and [2,3]. From station 3, we reach 2 and 0, giving 3.

The time complexity is O(n + e) and the space complexity is O(n).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

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;
}

Related Graph Challenges

Comments (0)

Join the Discussion

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

Metro Transfer Capacity Map

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Graph Challenges

City Signal Span

Memory Rune Sequencer

Shortest Path in Weighted Graph

Campus Shuttle Path with Dijkstra

DFS Graph Traversal

All Paths From Source to Target

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.