Metro Transfer Capacity Map

Published atDate not available

Array Easy 0 views

Like0

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

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 Array 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

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 Array Challenges

Riverside Power Grid Check

Campus Shuttle Loop Coverage

Harbor Ferry Route Planner

Skyway Signal Cluster

Museum Corridor Sweep

City Signal Span

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.