City Bus Loop Access

Tree Medium 1 views

Like27

City Bus Loop Access models reachability in a transport network with temporary closures. You are given a graph of stops and roads, a starting stop, and a set of closed stations that cannot be visited or used as transit points. The task is to compute how many unique open stops are reachable from the start following valid open paths.

The natural solution is graph traversal (BFS or DFS) with a visited set. Build adjacency from the road list, skip closed stations entirely, and explore only open neighbors. If the start itself is closed, the correct answer is immediately zero. Otherwise, count each distinct reachable stop once.

The judge tends to include disconnected graphs, redundant edges, isolated starts, and closure patterns that split the network into smaller components. Your implementation should be deterministic and robust for these variations. Return only the final reachable-count integer; no path reconstruction is needed. In short, this is a clean connectivity-count problem where closure constraints are part of traversal validity, not a post-processing filter.

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 = 5, roads = [[0,1],[1,2],[0,2],[2,3],[3,4]], start = 2, closed_stations = [4]

Output

Explanation

Stop 4 is closed, but the remaining stops 0, 1, 2, and 3 remain connected.

Example 2

Input

n = 4, roads = [[0,1],[1,2]], start = 3, closed_stations = []

Output

Explanation

Stop 3 has no connecting roads, so the bus stays at its origin.

Example 3

Input

n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[4,5]], start = 0, closed_stations = [3]

Output

Explanation

The bus visits stops 0, 1, and 2 before encountering the closed stop at 3.

Algorithm Flow

Recommendation Algorithm Flow for City Bus Loop Access - Budibadu

Best Answers

java

import java.util.*;

class Solution {
    public int city_bus_loop_access(int n, int[][] roads, int start, int[] closed_stations) {
        Set<Integer> closed = new HashSet<>();
        for (int s : closed_stations) closed.add(s);
        if (closed.contains(start)) return 0;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] road : roads) {
            adj[road[0]].add(road[1]);
            adj[road[1]].add(road[0]);
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(start);
        queue.add(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj[u]) {
                if (!visited.contains(v) && !closed.contains(v)) {
                    visited.add(v);
                    queue.add(v);
                }
            }
        }
        return visited.size();
    }
}

javascript

function city_bus_loop_access(n, roads, start, closed_stations) {
    const closed = new Set(closed_stations);
    if (closed.has(start)) return 0;
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of roads) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const u = queue.shift();
        for (const v of adj[u]) {
            if (!visited.has(v) && !closed.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }
    return visited.size;
}

php

<?php
function city_bus_loop_access($n, $roads, $start, $closed_stations) {
    $closed = array_flip($closed_stations);
    if (isset($closed[$start])) return 0;
    $adj = array_fill(0, $n, []);
    foreach ($roads as $road) {
        $u = $road[0];
        $v = $road[1];
        $adj[$u][] = $v;
        $adj[$v][] = $u;
    }
    $visited = [$start => true];
    $queue = [$start];
    while (!empty($queue)) {
        $u = array_shift($queue);
        foreach ($adj[$u] as $v) {
            if (!isset($visited[$v]) && !isset($closed[$v])) {
                $visited[$v] = true;
                $queue[] = $v;
            }
        }
    }
    return count($visited);
}
?>

python

from typing import List
from collections import deque

def city_bus_loop_access(n: int, roads: List[List[int]], start: int, closed_stations: List[int]) -> int:
    closed = set(closed_stations)
    if start in closed: return 0
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append(v)
        adj[v].append(u)
    visited = {start}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in visited and v not in closed:
                visited.add(v)
                queue.append(v)
    return len(visited)

rust

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

pub fn city_bus_loop_access(n: i32, roads: Vec<Vec<i32>>, start: i32, closed_stations: Vec<i32>) -> i32 {
    let closed: HashSet<i32> = closed_stations.into_iter().collect();
    if closed.contains(&start) { return 0; }
    let mut adj = vec![vec![]; n as usize];
    for road in roads {
        let u = road[0] as usize;
        let v = road[1] as usize;
        adj[u].push(v as i32);
        adj[v].push(u as i32);
    }
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    visited.insert(start);
    queue.push_back(start);
    while let Some(u) = queue.pop_front() {
        for &v in &adj[u as usize] {
            if !visited.contains(&v) && !closed.contains(&v) {
                visited.insert(v);
                queue.push_back(v);
            }
        }
    }
    visited.len() as i32
}

typescript

function city_bus_loop_access(n: number, roads: number[][], start: number, closed_stations: number[]): number {
    const closed = new Set(closed_stations);
    if (closed.has(start)) return 0;
    const adj: number[][] = Array.from({length: n}, () => []);
    for (const [u, v] of roads) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set<number>([start]);
    const queue: number[] = [start];
    while (queue.length > 0) {
        const u = queue.shift()!;
        for (const v of adj[u]) {
            if (!visited.has(v) && !closed.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }
    return visited.size;
}

Comments (0)

Join the Discussion

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

City Bus Loop Access

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Tree Problems

Chronicle Walkway Binding

Comments (0)

Join the Discussion