City Signal Span

Published at05 Jan 2026

Graph BFS Easy 47 views

Like1

Imagine looking after a city full of routes, signals, or stops. In City Signal Span, you are trying to work toward the right number by following one clear idea.

Calculate emergency broadcast signal span A good way to think about it is to first understand what goes in, then what rule you must follow, and finally what shape the answer should have.

For example, if the input is n = 4, roads = [[0,1],[1,2],[2,3]], start = 0, the answer is 4. The signal travels along every road and covers all four intersections. Another example is n = 6, roads = [[0,1],[1,2],[2,0],[3,4]], start = 5, which gives 1. Intersection 5 is isolated, so only the starting point receives the broadcast.

This is a friendly practice problem, but it still rewards careful reading. The key is understanding the rule clearly and then applying it carefully.

One helpful habit is to say the rule out loud in your own words before you start solving. If you can explain what counts, what changes, and what the final answer should look like, you are already much closer to the right solution.

Example Input & Output

Example 1

Input

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

Output

Explanation

The signal travels along every road and covers all four intersections.

Example 2

Input

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

Output

Explanation

Intersection 5 is isolated, so only the starting point receives the broadcast.

Example 3

Input

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

Output

Explanation

Intersections 0, 1, and 2 share a chain of roads, while 3 and 4 are separate.

Algorithm Flow

Recommendation Algorithm Flow for City Signal Span

Solution Approach

This problem asks us to count how many intersections the broadcast signal can reach from the starting point. The roads form an undirected graph, so the answer is the size of the connected component that contains the start.

A breadth-first search is the natural approach. We explore outward from the start along every road, marking each intersection we reach, and then return how many were visited.

Here is the implementation:

function count_reachable(n, roads, start) {
    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 curr = queue.shift();
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

We build an undirected adjacency list so each road connects both directions. Then we seed BFS with the start and expand through all reachable neighbors, marking each as visited. When the queue empties, the visited set holds exactly the component of the start, so its size is the answer.

Let us trace n = 4, roads = [[0,1],[1,2],[2,3]], start = 0. From intersection 0, we reach 1, then 2, then 3, so all four are visited and the answer is 4. For n = 6, roads = [[0,1],[1,2],[2,0],[3,4]], start = 5, intersection 5 has no roads, so only the start is counted, giving 1.

The time complexity is O(n + e) where e is the number of roads, 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 count_reachable(int n, int[][] roads, int start) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] road : roads) {
            adj.get(road[0]).add(road[1]);
            adj.get(road[1]).add(road[0]);
        }
        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 count_reachable(n, roads, start) {
    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 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 count_reachable($n, $roads, $start) {
    $adj = array_fill(0, $n, []);
    foreach ($roads as $road) {
        $adj[$road[0]][] = $road[1];
        $adj[$road[1]][] = $road[0];
    }
    $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 count_reachable(n: int, roads: List[List[int]], start: int) -> int:
    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:
        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 count_reachable(n: i32, roads: Vec<Vec<i32>>, start: i32) -> i32 {
    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);
        adj[v].push(u);
    }
    let mut visited = HashSet::new();
    visited.insert(start as usize);
    let mut queue = VecDeque::new();
    queue.push_back(start as usize);
    while let Some(curr) = queue.pop_front() {
        for &neighbor in &adj[curr] {
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                queue.push_back(neighbor);
            }
        }
    }
    visited.len() as i32
}

typescript

function count_reachable(n: number, roads: number[][], start: number): number {
    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([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.

City Signal Span

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

Memory Rune Sequencer

Shortest Path in Weighted Graph

Campus Shuttle Path with Dijkstra

DFS Graph Traversal

All Paths From Source to Target

Max Area of Island

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.