City Bus Loop Access

Tree Medium 0 views

Like27

Technical Goal

Implement a function to determine the number of distinct stops reachable from a starting origin in a circular bus system, where certain stops are closed and cannot be visited or traversed. The system is represented as an undirected graph.

Constraints

n: Total number of stops (0 to n-1).
roads: A list of two-way connections [u, v].
start: The origin stop index.
closed_stations: A list of indices representing unreachable stops.

Rules

If start is in closed_stations, return 0.
A path is only valid if all stops on the path (including start and the target stop) are not in closed_stations.
Return the total count of unique accessible stops reachable via open roads.

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.